# 兔子洞

By [baba](https://paragraph.com/@baba-2) · 2022-06-16

---

二分查找
----

题目示例：

    输入: nums = [-1,0,3,5,9,12], target = 9     
    输出: 4       
    解释: 9 出现在 nums 中并且下标为 4    
    

注意：数组是有序的！！！！

思路：

第一种方法：

我们定义 target 是在一个在左闭右闭的区间里，**也就是\[left, right\] （这个很重要非常重要）**。

区间的定义这就决定了二分法的代码应该如何写，**因为定义target在\[left, right\]区间，所以有如下两点：**

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

**左闭右闭区间**

    class Solution {
        public int search(int[] nums, int target) {
            // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
            if (target < nums[0] || target > nums[nums.length - 1]) {
                return -1;
            }
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] == target)
                    return mid;
                else if (nums[mid] < target)
                    left = mid + 1;
                else if (nums[mid] > target)
                    right = mid - 1;
            }
            return -1;
        }
    }
    

第二种方法：

定义 target 是在一个在左闭右开的区间里，也就是\[left, right)

*   while (left < right)，这里使用 < ,因为left == right在区间\[left, right)是没有意义的
    
*   if (nums\[middle\] > target) right 更新为 middle，因为当前nums\[middle\]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums\[middle\]
    

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

---

*Originally published on [baba](https://paragraph.com/@baba-2/dHn6kcjgAPx1UcKJZCAK)*