【Leetcode刷题】二分查找

第一种写法：我们每次查找的区间都是在[left,right](左闭右闭区间)，根据区间的定义，就可以决定后续的代码如何控制条件。

因为target定义在 [left, right] 区间，所以有如下两点：

• 循环条件要使用while(left <= right)，因为当left == right这种情况发生的时候，得到的结果是有意义的。
• if (nums[mid] > target)， right 要赋值为 mid- 1，因为当前这个nums[mid]一定不是target，那么接下来要查找的范围是[left, mid- 1]。

代码实现：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;// 记录数组最后一个元素下标
        while(left <= right)// 当left==right，区间[left, right]依然有效，所以用 <=
        {
            int mid = (left + right) / 2;//取中间元素下标

            if(nums[mid] > target)
            {
            	// target 在左区间，所以下一个查找范围[left, mid- 1]
                right = mid-1;
            }
            else if(nums[mid] < target)
            {
           	 	// target 在右区间，所以下一个查找范围[mid+ 1, right]
                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
18
19
20
21
22
23
24
25
26
27
28
29

4. 第二种写法（左闭右开）

第二种写法：我们每次查找的区间在[left,right)，若target定义在这种区间中， 那么二分法的边界处理方式则截然不同，有以下两点：

• 循环条件要使用while (left < right)，因为left == right在区间[left, right)是没有意义的
• if (nums[mid] > target)，right 更新为 mid，因为当前的 nums[mid] 是大于 target 的，不符合条件,不能取到 mid，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 mid。

代码实现：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();

        while(left < right)
        {
            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
18
19
20
21
22
23
24
25
26