【代码随想录】LC 704. 二分查找

2、时间复杂度

二分查找时间复杂度为O (log n)

3、代码详解

左闭右闭区间定义代码

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) / 2);
            //或
            //int mid = left + ((right - left) >> 1);
            int mid = (left + right) / 2;
            if (nums[mid] > target) right = mid - 1;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

左闭右开区间定义代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            //防止溢出可以改为：
            //int mid = left + ((right - left) / 2);
            //或
            //int mid = left + ((right - left) >> 1);
            int mid = (left + right) / 2;
            if (nums[mid] > target) right = mid;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三、知识风暴

1. 注意mid是下标不是值，与target比较时是用nums[mid]。
2. 防止溢出可以将int mid = (left + right) / 2;改为 int mid = left + ((right - left) / 2);或int mid = left + ((right - left) >> 1);。
3. 数组理论基础
   • 数组下标都是从0开始的
   • 数组在内存空间的地址是连续的
   • 数组中的元素只能覆盖，不能删除。