Binary Search Algorithm

Binary Search is a divide-and-conquer algorithm to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half:

  1. Initialize two pointers, low = 0 and high = n-1.
  2. While low ≤ high:
    • Compute mid = low + (high - low) / 2.
    • If arr[mid] == target, return mid.
    • If arr[mid] < target, set low = mid + 1.
    • Else, set high = mid - 1.
  3. If the loop ends without finding target, it is not in the array.

Time Complexity

Each step halves the search interval. In the worst case, you perform O(log n) comparisons.

Memory Complexity

The iterative version uses O(1) extra space. A recursive version would use O(log n) stack space.

Easy Problems

1. Search in Sorted Array

Given a sorted array arr and a target, return the index of target or -1 if not found.


#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9};
    cout << binarySearch(arr, 7) << endl; // Output: 3
    return 0;
}

2. First Occurrence of Target

Given a sorted array that may contain duplicates, find the first index where arr[i] == target, or -1 if absent.


#include <iostream>
#include <vector>
using namespace std;

int firstOccurrence(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1;  // continue searching left half
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main() {
    vector<int> arr = {1, 2, 2, 2, 3};
    cout << firstOccurrence(arr, 2) << endl; // Output: 1
    return 0;
}

Intermediate Problems

1. Search Insert Position

Given a sorted array and a target, return the index if the target is found. If not, return the index where it would be if inserted in order.


#include <iostream>
#include <vector>
using namespace std;

int searchInsert(const vector<int>& arr, int target) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < target) low = mid + 1;
        else high = mid;
    }
    return low;
}

int main() {
    vector<int> arr = {1, 3, 5, 6};
    cout << searchInsert(arr, 5) << endl; // Output: 2
    cout << searchInsert(arr, 2) << endl; // Output: 1
    return 0;
}

2. Search in Rotated Sorted Array

Given a rotated sorted array (no duplicates) and a target, find its index or -1 if not found.


#include <iostream>
#include <vector>
using namespace std;

int searchRotated(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;

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

int main() {
    vector<int> arr = {4,5,6,7,0,1,2};
    cout << searchRotated(arr, 0) << endl; // Output: 4
    return 0;
}

Hard Problem

Median of Two Sorted Arrays

Given two sorted arrays of size m and n, find the median of the combined sorted array in O(log(min(m,n))) time.


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) {
    if (A.size() > B.size()) return findMedianSortedArrays(B, A);

    int m = A.size(), n = B.size();
    int low = 0, high = m, half = (m + n + 1) / 2;

    while (low <= high) {
        int i = (low + high) / 2;
        int j = half - i;

        int Aleft  = (i == 0 ? INT_MIN : A[i-1]);
        int Aright = (i == m ? INT_MAX : A[i]);
        int Bleft  = (j == 0 ? INT_MIN : B[j-1]);
        int Bright = (j == n ? INT_MAX : B[j]);

        if (Aleft <= Bright && Bleft <= Aright) {
            if ((m + n) % 2 == 0)
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0;
            else
                return max(Aleft, Bleft);
        }
        else if (Aleft > Bright) {
            high = i - 1;
        }
        else {
            low = i + 1;
        }
    }
    return 0.0;
}

int main() {
    vector<int> A = {1, 3};
    vector<int> B = {2};
    cout << findMedianSortedArrays(A, B) << endl; // Output: 2.0
    return 0;
}