1. Introduction

Binary Search is an efficient algorithm to find the position of a target element in a sorted array by dividing the search interval in half repeatedly.

Unlike Linear Search, which checks elements one by one, Binary Search uses the divide and conquer approach to eliminate half of the array at each step.

2. Prerequisites

The array must be sorted in ascending (or consistently sorted) order for binary search to work correctly. If the array is unsorted, sort it first before applying binary search.

3. How Does Binary Search Work?

• Set the pointers:
  • low = 0
  • high = length - 1
• Find the middle index:
  • mid = (low + high) / 2
• Compare arr[mid] with the target:
  • If equal → return mid
  • If target < arr[mid] → search left half
  • If target > arr[mid] → search right half
• Repeat steps 2-3 until the target is found or low > high.

4. Iterative Implementation in Java

public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // avoids overflow

            if (arr[mid] == target) {
                return mid; // found
            } else if (target < arr[mid]) {
                high = mid - 1; // search left half
            } else {
                low = mid + 1; // search right half
            }
        }

        return -1; // not found
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, 17, 23, 35, 42, 56, 71};
        int target = 35;

        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found.");
        }
    }
}

5. Recursive Implementation in Java

public class RecursiveBinarySearch {

    public static int binarySearch(int[] arr, int low, int high, int target) {
        if (low > high) {
            return -1; // base case
        }

        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (target < arr[mid]) {
            return binarySearch(arr, low, mid - 1, target);
        } else {
            return binarySearch(arr, mid + 1, high, target);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, 17, 23, 35, 42, 56, 71};
        int target = 23;

        int result = binarySearch(arr, 0, arr.length - 1, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found.");
        }
    }
}

6. Time and Space Complexity

Operation	Time Complexity
Best Case	O(1) (first mid match)
Average Case	O(log n)
Worst Case	O(log n)
Space (iterative)	O(1)
Space (recursive)	O(log n) (due to recursion stack)

7. Common Mistakes

1. Using mid = (low + high)/2
   • This may cause integer overflow for large arrays.
   • Use mid = low + (high - low)/2 instead.
2. Array not sorted
   • Binary Search won’t work correctly on unsorted arrays.
3. Using == with floating-point or strings
   • Always use .equals() for objects like String.
4. Off-by-one errors
   • Carefully manage low and high bounds.