LeetCode 704. Binary Search 题解

LeetCode 704. Binary Search 题解

题目描述

给定一个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. 初始化左指针left为 0，右指针right为数组长度减 1。
  2. 当left <= right时，计算中间位置mid。
  3. 如果nums[mid] == target，返回mid。
  4. 如果nums[mid] < target，将left设为mid + 1。
  5. 如果nums[mid] > target，将right设为mid - 1。
  6. 如果循环结束仍未找到目标值，返回-1。

复杂度分析：

• 时间复杂度：O(log n)，其中 n 是数组的长度。每次查找都会将查找区间减半。
• 空间复杂度：O(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 # 如果没有找到目标值，返回 -1 return -1

测试用例

测试用例 1：

输入：nums = [-1,0,3,5,9,12], target = 9
输出：4

测试用例 2：

输入：nums = [-1,0,3,5,9,12], target = 2
输出：-1

总结

本题是搜索算法的经典问题，主要考察对二分查找算法的理解和实现。二分查找是一种在有序数组中查找特定元素的高效算法，它通过每次将查找区间减半来快速定位目标值。

二分查找的核心思想是：使用两个指针分别指向查找区间的两端，计算中间位置，比较中间元素与目标值的大小，根据比较结果缩小查找区间，直到找到目标值或确定目标值不存在。

这种方法的时间复杂度为 O(log n)，适用于大规模有序数据的查找。掌握二分查找的原理，对于理解搜索算法和算法设计思想非常重要。