Binary Search Algorithms: Basic Implementation, First/Last Occurrence, and Rotated Array Search

Binary search is a simple yet error‑prone algorithm; early implementations suffered from overflow bugs that were only fixed decades later (see "Programming Pearls"). This article summarizes binary search, its variants, and related problems.

Basic binary search – The standard implementation returns the index of the target if found, otherwise returns -(l+1) where l is the insertion position. The code is:

/**
 * 基本二分查找算法
 */
int binarySearch(int a[], int n, int t) {
    int l = 0, u = n - 1;
    while (l <= u) {
        int m = l + (u - l) / 2; // avoid overflow
        if (t > a[m])
            l = m + 1;
        else if (t < a[m])
            u = m - 1;
        else
            return m;
    }
    return -(l+1);
}

The return value -(l+1) is useful in algorithms such as consistent hashing and longest increasing subsequence, where the insertion point matters.

Finding the first occurrence – When the array contains duplicates, the following variant returns the index of the first occurrence or -1 if the target is absent:

/**
 * 二分查找第一次出现位置
 */
int binarySearchFirst(int a[], int n, int t) {
    int l = -1, u = n;
    while (l + 1 != u) {
        /* invariant: a[l] < t <= a[u] && l < u */
        int m = l + (u - l) / 2; // same as (l+u)/2
        if (t > a[m])
            l = m;
        else
            u = m;
    }
    int p = u;
    if (p >= n || a[p] != t)
        p = -1;
    return p;
}

Finding the last occurrence – A symmetric version returns the last position:

/**
 * 二分查找最后一次出现位置
 */
int binarySearchLast(int a[], int n, int t) {
    int l = -1, u = n;
    while (l + 1 != u) {
        /* invariant: a[l] <= t < a[u] */
        int m = l + (u - l) / 2;
        if (t >= a[m])
            l = m;
        else
            u = m;
    }
    int p = l;
    if (p <= -1 || a[p] != t)
        p = -1;
    return p;
}

A combined routine can return either the first or last occurrence based on a flag, reusing the basic binary‑search loop with additional checks.

Searching in a rotated sorted array – The problem is to locate a target in an array that has been rotated unknown number of positions. Two solutions are presented:

Two‑phase binary search: first find the rotation index, then binary‑search the appropriate sub‑array.

Single‑phase binary search: at each step determine which half is sorted and narrow the search accordingly.

Two‑phase implementation:

/**
 * 旋转数组查找-两次二分查找
 */
int binarySearchRotateTwice(int a[], int n, int t) {
    int p = findRotatePosition(a, n); // rotation point
    if (p == -1)
        return binarySearchFirst(a, n, t);
    int left = binarySearchFirst(a, p+1, t);
    if (left != -1)
        return left;
    int right = binarySearchFirst(a+p+1, n-p-1, t);
    if (right == -1)
        return -1;
    return right + p + 1;
}

/**
 * 查找旋转位置
 */
int findRotatePosition(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        if (a[i+1] < a[i])
            return i;
    }
    return -1;
}

Single‑phase implementation:

/**
 * 旋转数组二分查找-一次二分查找
 */
int binarySearchRotateOnce(int a[], int n, int t) {
    int l = 0, u = n-1;
    while (l <= u) {
        int m = l + (u-l) / 2;
        if (t == a[m])
            return m;
        if (a[m] >= a[l]) { // left half sorted
            if (t >= a[l] && t < a[m])
                u = m - 1;
            else
                l = m + 1;
        } else { // right half sorted
            if (t > a[m] && t <= a[u])
                l = m + 1;
            else
                u = m - 1;
        }
    }
    return -1;
}

Both approaches guarantee O(log n) time and O(1) extra space.

References

Programming Pearls, 2nd edition, Chapter 9 http://www.jobcoding.com/datastructure-and-algorithm/array/one-sorted-array/rotate_array/

Source: juejin.im/post/5baba2eaf265da0aea698244