二分查找

基本思想

• 二分查找针对的是一个有序的数据集合，利用类似分治的思想：每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
• 二分查找的时间复杂度为O(logn)，是一种极其高效的时间复杂度。

代码实现

int bsearchSimple(const vector<int> &a, int n, int value) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] < value) {
            low = mid + 1;
        } else if (a[mid] > value) {
            high = mid - 1;
        } else {
            return mid;
        }
    }

    return -1;
}

注意以下几个易错点：

• 循环退出条件
  • 注意是low<=high，而不是low<high。
• mid 的取值
  • mid=(low+high)/2
  • 改进1：mid=low+(high-low)/2。防止 low 和 high 比较大的情况，两者之和有可能会溢出。
  • 改进2：mid=low+((high-low)>>1)。将除以 2 运算转化成位运算，计算机处理位运算要比除法运算快得多。
• low 和 high 的更新
  • low=mid+1, high=mid-1。注意这里的 +1 和 -1，如果直接写成low=mid, high=mid，可能会发生死循环。

应用场景

• 二分查找依赖的是顺序表结构
  • 二分查找底层依赖数组
• 二分查找针对的是有序数据
  • 只能用在插入、删除操作不频繁，一次排序多次查找的场景中；
    • 针对动态数据集合快速查找某个数据：二叉树。
• 数据量太小或太大都不适合二分查找
  • 数据量小：顺序查找即可；
  • 数据量大：用数组存储会比较吃力（数组要求内存空间连续），也就不适合使用二分查找了；
  • 特殊情况：如果数据之间的比较操作非常耗时，不管数据量大小都推荐使用二分查找，尽可能减少比较次数。

经典变体

查找第一个等于value的元素

int bsearch_1(const vector<int> &a, int value) {
    int low = 0, high = a.size() - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] > value) {
            high = mid - 1;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            if ((mid == 0) || (a[mid - 1] != value)) {
                return mid;
            } else {
                high = mid - 1;
            }
        }
    }

    return -1;
}

查找最后一个等于value的元素

int bsearch_2(const vector<int> &a, int value) {
    int low = 0, high = a.size() - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] > value) {
            high = mid - 1;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            if ((mid == a.size() - 1) || (a[mid + 1] != value)) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }

    return -1;
}

查找第一个大于等于value的元素

int bsearch_3(const vector<int> &a, int value) {
    int low = 0, high = a.size() - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] >= value) {
            if ((mid == 0) || (a[mid - 1] < value)) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

查找最后一个小于等于value的元素

int bsearch_4(const vector<int> &a, int value) {
    int low = 0, high = a.size() - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] <= value) {
            if ((mid == a.size() - 1) || (a[mid + 1] > value)) {
                return mid;
            } else {
                low = mid + 1;
            }
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

LeetCode例题 33 (opens new window)

Search in Rotated Sorted Array（搜索旋转排序数组）

• 思路1：二分查找旋转下标，分成两个有序数组，分别做两个简单二分查找。
• 注意这里循环退出条件和low和high的更新不同于简单二分查找，需要仔细斟酌。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int rotation_index = 0;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] > nums[mid + 1]) {
                rotation_index = mid + 1;
                break;
            }
            if (nums[mid] > nums[l]) { l = mid; }
            if (nums[mid] < nums[r]) { r = mid; }
        }
        int l_res = binarySearch(nums, 0, rotation_index - 1, target);
        int r_res = binarySearch(nums, rotation_index, nums.size() - 1, target);

        return l_res == -1 ? r_res : l_res;
    }

    int binarySearch(vector<int> &nums, int start, int end, int target) {
        int l = start, r = end;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] < target) { l = mid + 1; }
            else if (nums[mid] > target) { r = mid - 1; }
            else { return mid; }
        }
        return -1;
    }
};

Search in Rotated Sorted Array

思路2：二分之后，总有一半是有序数组，另一半是循环数组。

class Solution {
public:
    int search(vector<int>& a, int value) {
        int low = 0, high = a.size() - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] == value) { return mid; }

            if (a[mid] >= a[low]) { // 前半部分为有序数组
                if ((a[mid] > value) && (a[low] <= value)) { // value在有序部分
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else { // 后半部分为有序数组
                if ((a[mid] < value) && (a[high] >= value)) { // value在有序部分
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }

        return -1;
    }
};