Binary Search in Java

Binary Search in Java

Binary Search Algorithm

Binary Search works on sorted arrays and uses divide-and-conquer:

  1. Find the middle element.
  2. If it matches the target, return the index.
  3. If target < middle, search the left half.
  4. If target > middle, search the right half.
  5. Repeat until found or range is empty.

Time complexity: O(log n)
Space complexity: O(1) for iterative, O(log n) for recursive (due to call stack)

Iterative Binary Search

public class BinarySearchIterative {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // Prevents overflow

            if (arr[mid] == target) {
                return mid; // Found
            } else if (arr[mid] < target) {
                left = mid + 1; // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }
        return -1; // Not found
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56};
        int target = 23;

        int index = binarySearch(arr, target);
        if (index != -1)
            System.out.println("Element found at index: " + index);
        else
            System.out.println("Element not found!");
    }
}

Output:

Element found at index: 5

Recursive Binary Search

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1; // Base case: not found
        }

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, right, target); // Search right half
        } else {
            return binarySearch(arr, left, mid - 1, target); // Search left half
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56};
        int target = 12;

        int index = binarySearch(arr, 0, arr.length - 1, target);
        if (index != -1)
            System.out.println("Element found at index: " + index);
        else
            System.out.println("Element not found!");
    }
}

Notes:

  • Array must be sorted before using Binary Search.
  • To avoid integer overflow, use: mid = left + (right - left)/2 instead of (left + right)/2.
  • Iterative is more memory-efficient; recursive is elegant and easier to read.

Leave a Reply