704. 二分查找

力扣题目链接(opens new window)

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

示例 1:

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

1
2
3

示例 2:

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

1
2
3

提示：

• 你可以假设 nums 中的所有元素是不重复的。

• n 将在 [1, 10000]之间。

• nums 的每个元素都将在 [-9999, 9999]之间。

写前须知

1. 数学上，(left + right) / 2 是区间的中点。

2. 编程中，由于整数除法，它会偏向左侧（偶数长度时）。

3. 我们主要讨论区间范围的变换通过一个中间值(前提是该数组已经有序)去判断我们想要的的target在区间的左边或者右边

4. 除开中间值恰好等于target的情况，会出现小于大于情况，这时需要去更改区间范围与中间值

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int mid = (left + right) / 2;
        while (left <= right) {
            if (target > nums[mid]) {
                left = mid + 1;
            }
			else if (target < nums[mid]) {
				right = mid - 1;
			}
			else {
				return mid;
			}
            mid = (left + right) / 2;
        }
        return -1; // 如果未找到目标值，返回 -1
    }
};

返回插入位置

1. 目标值最小（插入位置为0）：

   • 您的描述：右边界不断缩小直到与第一位重合，然后右边界减1（变为-1），返回 rightIndex + 1 = 0。

   • 正确性：正确。例如 nums = [1,3,5], target = 0，结束时 rightIndex = -1，返回 0。

2. 目标值最大（插入位置为数组末尾）：

   • 您的描述：右侧边界保持不动，左侧边界移动，返回 rightIndex + 1。

   • 正确性：正确。例如 nums = [1,3,5], target = 6，结束时 rightIndex = 2，返回 3（即 nums.size()）。

3. 目标值在两个元素之间：

   • 您的描述：存在大于 target 的数，右边界减1，返回 rightIndex + 1。

   • 正确性：正确。例如 nums = [1,3,5], target = 2，结束时 rightIndex = 0，返回 1（插入在索引1）。

   • 注意：循环结束时，leftIndex = rightIndex + 1，因此返回 rightIndex + 1 等价于返回 leftIndex（这是标准二分查找插入位置的写法）。

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