# \[704]\[中等]\[二分] 二分查找

0# 题目描述

[704. 二分查找](https://leetcode-cn.com/problems/binary-search/)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

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

示例 2:

```
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
```

提示：

* 你可以假设 nums 中的所有元素是不重复的。
* n 将在 \[1, 10000]之间。
* nums 的每个元素都将在 \[-9999, 9999]之间。

## 解题思路

[二分查找详解](https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/er-fen-cha-zhao-xiang-jie)

### 两种终止条件带来的细节变化

要注意, **right的起始位置**, **while循环的终止条件**, **left和right移动规则**等细节之间, 是相互关联的.

本题中, 如果假设**while的终止条件为`left <= right`**, 相当于`left`和`right`定义的区间`[left, right]`两端都有效, 是**闭区间**, 因此在初始化`right`时, 应初始化为`n - 1`, `n`是列表的长度.

而且由于左右端都是闭的, `right`在移动时, 应当为`right = mid - 1`, 因为`nums[mid]`经过检测不符合条件, 不能被包含在下一个区间之内.

对应的代码为:

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
```

但如果**while的终止条件为`left < right`**, 换句话说当`left == right`时就终止了, 可以**认为`right`代表的位置是无效的**, **越界的**, 因此`left`与`right`相等时, 代表都越界了, 从而停止. 它们定义的区间为`[left, right)`, 左闭右开. 而且在初始化`right`时, 因为要求越界, 应初始化为`n`.

另外, 在移动`right`时, 当`mid`位置的数值无效, 应当移动`right`时, 应当为`right = mid`, 当前`mid`位置是经过判别无效的, 因此放弃这个位置, 为新区间的开边界.

但需要注意的是, 如果`left == right`是通过移动`right`得到的, 那么在`while`停止的时候, `left`(也即`mid`和`right`)的位置是没有经过判别的, 因此在最后返回之前, 要再对这个位置**单独的进行一次判别**.

对应的代码为:

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left if nums[left] == target else -1
```

### 寻找左侧边界的二分搜索

对于有序数组`nums = [1,2,2,2,3]`, `target`为`2`, 使用上面任何一种方法得到的索引结果都是`2`, 即三个`2`中间的`2`对应的索引. 但如果要求变为, 对于重复的数字, 返回**最左侧**的索引呢?

第一个变化是, 当我们遇到`nums[mid] == target`时, 不能直接就返回了, 而是应该继续搜索. 关键问题是当遇到相等的情况, 应当怎么移动.

无论终止条件是`left < right`或`left <= right`, 在遇到`nums[mid] == target`时, 都应当移动`right`, 且移动的方法与`nums[mid] > target`的情况保持一致, 即:

* 终止条件是`left < right`: `right = mid`
* 终止条件是`left <= right`: `right = mid - 1`

对于第一种情况(`left < right`), 遇到`target`在列表中有多个值的情况, `right`在遇到`target`值之后, 只会逐渐向左移动, 直到移动到最左侧的`target`位置, 之后`right`就不可能再动了, 因为会一直满足`nums[mid] < target`, 导致`left`一直右移, 直到`left == right`结束.

第二种情况(`left <= right`), 在遇到`target`值之后, `right`也是会一直向右移动, 但与第一种情况不同的是, `right`一直在当前`target`之前的一位, 直到移动到最左侧的`target`前一位, 之后就是同样的`left`不断左移, 直到`left > right`, 即`left == right + 1`结束, 此时的`left`就是最左侧`target`的位置.

第一种情况(`left < right`)代码:

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                right = mid
            elif nums[mid] > target:
                right = mid
            elif nums[mid] < target:
                left = mid + 1

        if left == len(nums):
            return -1
        return left if nums[left] == target else -1
```

第二种情况(`left <= right`)代码:

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                right = mid - 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1

        if left == len(nums):
            return -1
        return left if nums[left] == target else -1
```

### 寻找右侧边界的二分查找

分析同上, 只是遇到相等的情况, 需要移动`left`.

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid
            elif nums[mid] < target:
                left = mid + 1

        if left == 0:
            return -1
        return left - 1 if nums[left - 1] == target else -1
```

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1

        if left == 0:
            return -1
        return left - 1 if nums[left - 1] == target else -1
```