# \[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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/er-fen/704-er-fen-cha-zhao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.