类型推导

# 查找
关于查找，有几种经典的数据类型：
- 树
- 散列表
- 链表

## 二分查找
最简单粗暴的场景， 是**无序结构中进行顺序查找**，这种方法，显而易见复杂度较高。

进一步将问题延伸，就有了**顺序结构中的查找**，这里引出二分查找方法。

二分查找的精髓，一是有序，二是较易寻址。其中第二条，意味著二分查找天然适合数组类型，而对于链表这种不连续的存储结构，不太适用。我们先用数组，来介绍经典的二分查找方法。


 简单描述二分查找的几个步骤（以升序为例）：
 1. 如果中间位置，等于目标值，表示已经查到；
 2. 如果中间位置，小于目标值，则在后半部分，重复查找；
 3. 如果中间位置，大于目标值，则在前半部分，重复此步骤继续查找。

 ### 二分查找算法框架：
 ```c++
 int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = ...;//注意

    while(...) {//注意
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...//注意
        } else if (nums[mid] < target) {
            left = ...//注意
        } else if (nums[mid] > target) {
            right = ...//注意
        }
    }
    return ...;//注意
}
```
需要关注的点：

- 循环条件
- 判断和目标值相等的处理
- 左边界和右边界如何变化



###  经典二分查找算法
> 经典二分查找算法是最简单的，即搜索一个数，如果存在，返回其索引，否则返回 -1。


```c++
int binarySearch(vector<int>& nums, int target) {
    int left = 0; 
    int right = nums.size()- 1; // 注意

    while(left <= right) {//注意
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}
```

### 寻找左边界

> 问题引出：如果待查找数在有序数组中是重复数字，那么上述算法虽然可以查找出一个正确的解，但是不能查找到处于边界的数字索引。比如有序数组nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，该解没错。但是如果我想得到 target的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。这样的需求很常见，你也许会说，找到一个target，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的复杂度了。

 核心思想是判断跳出循环的状态，以及设置 nums[mid] = target 时，该如何进行下一步。
 
 一个简单的想法，寻找左边界即：
 1. 当 nums[mid] == target 时，继续向左搜索，收缩右边界；
 2. 直到 left > right 时跳出循环，此时 left 应为目标位置，对其进行越界判断即可。

```c++
int leftBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size()-1; // 注意
	// 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 注意：收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.size() || nums[left] != target)
        return -1;
    return left;
}
```

### 寻找右边界
 跟寻找左边界类似，直接上代码
 ```c++
 int rightBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}
 ```

《算法》：搜索

![infinity-7345548.jpg](http://212.64.0.72/static/img/57ac1f77a76f6edc8ebc583708576934.infinity-7345548.webp)
# 你好，开篇
这里是 2025 年 2 月 8 日，blog 初始。