Binary Search Basics

binary_search.md

1. Classical Binary Search

• Binary search only works on sorted arrays. For unsorted arrays, the fastest way to find an element is linear scan O(n).
• It can be implemented either by iteration or recursion. Since recursion has higher space complexity but no gains in time complexity, we prefer iteration implementation.
• The physical interpretation of left and right is that the element to find must reside in the range [left, right].
• The worst case of time complexity happens when the element to find does not exist in the array.

/* iteration version: T[O(logn)], S[O(1)] */
int binarySearch(vector<int> &arr, int target)
{
    if (arr.empty())
        return -1;
        
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

/* recursion version: T[O(logn)], S[O(logn)] */
int helper(vector<int> &arr, int target, int left, int right)
{
    if (left > right)
        return -1;
        
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return helper(arr, target, mid + 1, right);
    } else {
        return helper(arr, target, left, mid - 1);
    }
}

int binarySearch2(vector<int> &arr, int target)
{
    if (arr.empty())
        return -1;
    return helper(arr, target, 0, arr.size() - 1);
}

2. Find the first occurance

int searchFirst(vector<int> &arr, int target)
{
    if (arr.empty()) return -1;
    
    int left = 0, right = arr.size() - 1;
    while (left < right - 1) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) 
            right = mid;
        else
            left = mid; // avoid out of bound when dereferencing arr[left]
    }
 
    if (arr[left] == target) return left;
    if (arr[right] == target) return right;
    return -1;
}

3. Find the last occurance

int searchLast(vector<int> &arr, int target)
{
    if (arr.empty()) return -1;
    
    int left = 0, right = arr.size() - 1;
    while (left < right - 1) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) 
            left = mid;
        else
            right = mid; // avoid out of bound when dereferencing arr[right]
    }
 
    if (arr[left] == target) return left;
    if (arr[right] == target) return right;
    return -1;
}