leetcode 704 二分查找

704. 二分查找

已解答

简单

相关标签

相关企业

给定一个 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

提示：

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

---

from typing import Listclass Solution:def search(self, nums: List[int], target: int) -> int:# 初始化左边界和右边界left, right = 0, len(nums) - 1# 当左边界小于等于右边界时，继续搜索while left <= right:# 计算中点索引，避免直接相加导致溢出mid = (right - left) // 2 + leftnum = nums[mid]  # 获取中点位置的元素# 检查中点位置的元素是否等于目标值if num == target:return mid  # 如果找到了目标值，返回中点索引# 如果中点的元素大于目标值，缩小右边界至中点的左侧elif num > target:right = mid - 1# 如果中点的元素小于目标值，缩小左边界至中点的右侧else:left = mid + 1# 如果循环结束仍未找到目标值，返回 -1return -1

注释解释

1. 初始化左右边界:
   left 设置为数组的起始位置 0，right 设置为数组的末尾位置 len(nums) - 1，表示我们将要在整个数组范围内查找目标值。

2. 循环条件:
   通过 while left <= right 控制搜索范围，当 left 超过 right 时，说明目标值不存在于数组中，退出循环。

3. 计算中点:
   mid = (right - left) // 2 + left 用于计算当前 left 和 right 之间的中点，保证计算不会因直接相加而导致溢出问题。

4. 目标值检查:

   • 如果找到了目标值 nums[mid] == target，直接返回 mid 索引，算法结束。
   • 如果目标值比中点元素小 num > target，说明目标值在中点左侧，因此将 right 更新为 mid - 1，缩小搜索范围。
   • 如果目标值比中点元素大 num < target，说明目标值在中点右侧，因此将 left 更新为 mid + 1。

5. 返回 -1:
   如果循环结束且没有找到目标值，则返回 -1 表示目标值不存在于数组中。
    

   class Solution {public int search(int[] nums, int target) {// 初始化左右边界int left = 0, right = nums.length - 1;// 当左边界小于等于右边界时，继续二分查找while (left <= right) {// 计算中点索引，避免直接相加导致溢出int mid = (right - left) / 2 + left;int num = nums[mid]; // 获取中点位置的元素// 检查中点位置的元素是否等于目标值if (num == target) {return mid; // 如果找到目标值，返回中点索引} // 如果中点元素大于目标值，则缩小搜索范围到左半边else if (num > target) {right = mid - 1;} // 如果中点元素小于目标值，则缩小搜索范围到右半边else {left = mid + 1;}}// 如果循环结束仍未找到目标值，返回 -1return -1;}
   }
   

二分查找 为什么mid = right // 2这样不行 需要mid = (right - left) // 2 + left

在二分查找中，mid的计算需要使用(right + left) // 2或(right - left) // 2 + left，而不是right // 2。这是因为mid = right // 2会导致错误的中点计算，特别是在left不为0的情况下。这里是原因的具体分析：

1. 错误的中点计算：当你直接用mid = right // 2时，计算出的中点并没有考虑left的偏移量。这会导致在某些情况下，特别是当left不为0时，mid指向数组的错误位置，从而导致算法无法正常工作。

2. 正确的中点计算：mid = (right + left) // 2或mid = (right - left) // 2 + left能够动态计算出当前搜索范围的中点位置，从而确保了二分查找的正确性。

   • right - left确保了范围的长度。
   • + left将中点偏移到当前搜索范围的开头，避免忽略left的影响。

3. 避免溢出：在某些编程语言中，直接用(right + left) // 2可能导致溢出（如果right和left都很大），而(right - left) // 2 + left可以规避这一问题（Python中不存在这个问题，因为它的int是动态扩展的）。

因此，推荐使用 mid = (right + left) // 2 或 mid = (right - left) // 2 + left 来确保算法的正确性和稳定性。