泰安网站建设入门推荐网站功能图
LeetCode-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
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
解题思路一：注意开区间和闭区间
# lower_bound 返回最小的满足 nums[i] >= target 的 i
# 如果数组为空，或者所有数都 < target，则返回 len(nums)
# 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]# 闭区间写法
def lower_bound(nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1 # 闭区间 [left, right]while left <= right: # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right+1] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1 # 范围缩小到 [mid+1, right]else:right = mid - 1 # 范围缩小到 [left, mid-1]return left # 或者 right+1# 左闭右开区间写法
def lower_bound2(nums: List[int], target: int) -> int:left, right = 0, len(nums) # 左闭右开区间 [left, right)while left < right: # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1 # 范围缩小到 [mid+1, right)else:right = mid # 范围缩小到 [left, mid)return left # 或者 right# 开区间写法
def lower_bound3(nums: List[int], target: int) -> int:left, right = -1, len(nums) # 开区间 (left, right)while left + 1 < right: # 区间不为空mid = (left + right) // 2# 循环不变量：# nums[left] < target# nums[right] >= targetif nums[mid] < target:left = mid # 范围缩小到 (mid, right)else:right = mid # 范围缩小到 (left, mid)return right # 或者 left+1class Solution:def search(self, nums: List[int], target: int) -> int:i = lower_bound(nums, target) # 选择其中一种写法即可return i if i < len(nums) and nums[i] == target else -1
时间复杂度：O(logn)
空间复杂度：O(1)
背诵版：
class Solution:def search(self, nums: List[int], target: int) -> int:l = 0r = len(nums) - 1while l <= r:mid = (l + r) // 2if nums[mid] > target:r = mid - 1elif nums[mid] < target:l = mid + 1else:return midreturn -1
时间复杂度：O(logn)
空间复杂度：O(1)
解题思路三：
时间复杂度：O(logn)
空间复杂度：O(1)
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠