源码如何做网站,轻量级网站开发,泉州网站关键词推广,百度惠生活商家入驻LeetCode-704. 二分查找【数组 二分查找】 题目描述#xff1a;解题思路一#xff1a;注意开区间和闭区间背诵版#xff1a;解题思路三#xff1a; 题目描述#xff1a;
给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xf… 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[right1] targetmid (left right) // 2if nums[mid] target:left mid 1 # 范围缩小到 [mid1, right]else:right mid - 1 # 范围缩小到 [left, mid-1]return left # 或者 right1# 左闭右开区间写法
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 # 范围缩小到 [mid1, 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 # 或者 left1class 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) 创作不易观众老爷们请留步… 动起可爱的小手点个赞再走呗 (๑◕ܫ๑) 欢迎大家关注笔者你的关注是我持续更博的最大动力 原创文章转载告知盗版必究 ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠
