二分查找

题目：

给定一个整型有序数组nums和一个目标之target,写一个搜索函数搜索target,如果存在则返回target在数组中的下下标，如果target不存在，返回-1。

代码

思路：

  1. 采取闭区间[left,right]写法
  2. while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  3. if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

复杂度：

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int search::solution(vector<int>&nums,int target)
{
   int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1; 
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。