二分查找算法原理与 C++ 实现详解

二分查找

题目解析

查看题目条件，使用双指针并非最优解，应采用二分法。

算法原理

二分法本质是将有序序列不断折半缩小查找范围，时间复杂度为 O(log n)。 核心细节：

1. 循环条件：left <= right，防止越界。
2. 找中点：left + (right - left) / 2 或 left + (right - left + 1) / 2，防止溢出。
3. 朴素二分查找模版：

   while(left <= right) {
       int mid = left + (right - left) / 2;
       if(条件) left = mid + 1;
       else if(条件) right = mid - 1;
       else return ...;
   }
   

编写代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return -1;
    }
};

在排序数组中查找元素的第一个和最后一个位置

题目解析

需分别查找目标值的起始和结束位置。