查找

关于查找，有几种经典的数据类型：

• 树
• 散列表
• 链表

二分查找

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

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

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

简单描述二分查找的几个步骤（以升序为例）：

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;
}