Binary Search

Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the value of the target is less than the middle element of the array, the search continues in the lower half. If the value of the target is greater than the middle element, the search continues in the upper half. This process continues until the target value is found or the search interval is empty.

Implementation

Pseudocode

procedure binarySearch(A : sorted list of items, target : item)
    low = 0
    high = length(A) - 1
    while low <= high do
        mid = (low + high) / 2
        if A[mid] = target then
            return mid
        else if A[mid] < target then
            low = mid + 1
        else
            high = mid - 1
        end if
    end while
    return -1
end procedure

Java

public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

Runtime Analysis

Given $N$ elements in the sorted array, the time complexity of binary search is $\Theta (\log N)$.

Best Case

The best case occurs when the target value is found at the middle position of the array. The time complexity is $\Omega (1)$.

Worst Case

The worst case occurs when the target value is not present in the array or is found at the last position in the array. In this case, the algorithm makes $\log N$ comparisons. The time complexity is $O(\log N)$.

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.