Binary Search in Java

Binary Search in Java

Binary Search is a highly efficient algorithm to search for an element in a sorted array or list. It works by repeatedly dividing the search interval in half. If the value of the target is less than the middle element, the search continues in the left half; if greater, it continues in the right half. This process repeats until the target value is found or the interval becomes empty.

Binary Search Algorithm:

1. Initialize two pointers: low and high, which represent the search boundaries.

2. Find the middle element: Calculate the mid index.

3. Compare the middle element with the target:

   • If the middle element is equal to the target, return the index.

   • If the target is smaller than the middle element, search the left half (high = mid - 1).

   • If the target is larger, search the right half (low = mid + 1).

4. Repeat the process until the search interval is exhausted (i.e., low > high).

Java Code Example

public class BinarySearch {

    // Iterative approach
    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;  // To avoid overflow

            if (arr[mid] == target) {
                return mid;  // Found target, return index
            } else if (arr[mid] < target) {
                low = mid + 1;  // Target is in the right half
            } else {
                high = mid - 1;  // Target is in the left half
            }
        }
        return -1;  // Target not found
    }

    public static void main(String[] args) {
        int[] sortedArray = {2, 5, 7, 10, 14, 20, 23, 34, 56, 78};
        int target = 20;
        int result = binarySearch(sortedArray, target);

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

Time Complexity:

• Best Case: O(1) when the middle element is the target.

• Average and Worst Case: O(log n) because the search space is halved after every iteration.

Space Complexity:

• Iterative: O(1)

• Recursive: O(log n) due to the recursive call stack.

Common Interview Questions Based on Binary Search

Here are some popular and efficient binary search interview questions:

1. Find the first and last position of an element in a sorted array:

   • Given a sorted array, return the starting and ending index of a given target value.

   • This can be done by performing two binary searches (one for the first occurrence and another for the last).

2. Find the square root of a number:

   • Without using a library function, find the square root of a given non-negative integer using binary search.

3. Search in a rotated sorted array:

   • In a sorted array that has been rotated at some pivot unknown to you, find the target element in O(log n) time.

4. Find peak element:

   • Given an array of integers where every element is unique, find a peak element (an element that is greater than its neighbors) using binary search in O(log n) time.

5. Find minimum in a rotated sorted array:

   • A sorted array is rotated at some pivot. Find the minimum element using binary search.

6. Median of two sorted arrays:

   • Given two sorted arrays, find their median. The expected time complexity is O(log(min(n, m))) where n and m are the sizes of the two arrays.

7. Allocate minimum number of pages:

   • Given a set of books and students, assign books to students such that the maximum number of pages assigned to a student is minimized using binary search.

8. Search in a nearly sorted array:

   • Given a nearly sorted array where each element may be moved by at most one position, find a target element in O(log n) time using binary search.