LeetCode 704. 二分查找【二分】-白红宇

LeetCode 704. 二分查找【二分】

阅读量：799 次

发布时间：2023-04-16

本文共 1123 字，大约阅读时间需要 3 分钟。

二分查找是一种高效的查找算法，尤其适用于已排序的数组。以下是实现二分查找的步骤：

初始化指针：设置left指针为数组起始位置，right指针为数组末尾位置。

计算中间指针mid：通过将left和right的平均值向下取整来计算mid的位置。

比较目标值：如果target等于nums[mid]，返回mid的值。

调整查找方向：

如果target大于nums[mid]，则目标值可能位于右半部分，调整left指针到mid+1。

否则，目标值可能位于左半部分，调整right指针到mid-1。

终止条件：当left超过right时，说明目标值不存在，返回-1。

以下是实现代码：

class Solution:    def search(self, nums: List[int], target: int) -> int:        left = 0        right = len(nums) - 1        while left <= right:            mid = left + (right - left) // 2            if nums[mid] == target:                return mid            elif nums[mid] < target:                left = mid + 1            else:                right = mid - 1        return -1

示例分析：

示例1：nums = [-1,0,3,5,9,12], target = 9
- 初始化left=0，right=5，mid=2，nums[2]=3 < 9，调整left=3。
- 现在left=3，right=5，mid=4，nums[4]=9，找到目标，返回4。

示例2：nums = [-1,0,3,5,9,12], target = 2
- 初始化left=0，right=5，mid=2，nums[2]=3 > 2，调整right=1。
- 现在left=0，right=1，mid=0，nums[0]=-1 < 2，调整left=1。
- left=1，right=1，mid=1，nums[1]=0 < 2，调整left=2。
- 循环结束，返回-1。