手机软件定制开发公司,优化大师好用吗,seo的中文含义,专业网站建设服务包括文章目录 1 二分查找算法2 二分查找细节3 二分查找两种思路3.1 直接法3.2 排除法 1 二分查找算法
二分查找算法是一种常用的查找算法#xff0c;也被称为折半查找算法。它适用于有序数组的查找#xff0c;并通过将待查找区间不断缩小一半的方式来快速定位目标值。
算法思想… 文章目录 1 二分查找算法2 二分查找细节3 二分查找两种思路3.1 直接法3.2 排除法 1 二分查找算法
二分查找算法是一种常用的查找算法也被称为折半查找算法。它适用于有序数组的查找并通过将待查找区间不断缩小一半的方式来快速定位目标值。
算法思想如下
首先确定待查找数组的起始位置通常为数组的第一个元素和结束位置通常为数组的最后一个元素。然后计算待查找区间的中间位置即将起始位置和结束位置相加除以2。比较中间位置的元素与目标值的大小关系
如果中间位置的元素等于目标值则查找成功返回中间位置。如果中间位置的元素大于目标值则目标值可能在左半部分将结束位置更新为中间位置的前一个位置。如果中间位置的元素小于目标值则目标值可能在右半部分将起始位置更新为中间位置的后一个位置。
重复步骤2和步骤3直到找到目标值或者待查找区间为空起始位置大于结束位置为止。
二分查找算法的时间复杂度为 O ( log n ) O(\log n) O(logn) 其中 n n n 为数组的大小。由于每次查找都将待查找区间缩小一半因此它比线性查找算法更加高效。
2 二分查找细节
区间开闭问题
左闭右闭区间注意初始化时 r i g h t l e n ( n u m s ) − 1 right len(nums)-1 rightlen(nums)−1数组最后一个元素位置。左闭右开区间注意初始化时 r i g h t l e n ( n u m s ) right len(nums) rightlen(nums)数组最后一个元素的下一个位置。一般情况全部使用「左闭右闭区间」这种写法。 m i d mid mid 取值问题
常见的两种取值公式
mid (left right) // 2 # 使用较多
mid (left right 1) // 2当待查找区间中的元素个数为奇数个使用这两种取值公式都能取到中间元素的下标位置。当待查找区间中的元素个数为偶数个 mid (left right) // 2 能取到中间靠左边元素的下标位置。mid (left right 1) // 2 能取到中间靠右边元素的下标位置。
出界条件的判断
两种判断方式
left right
left rightleft right并且查找的元素不在有序数组中则 while 语句的出界条件是 left right也就是 left right 1写成区间形式就是 [ r i g h t 1 right1 right1, r i g h t right right]此时待查找区间为空待查找区间中没有元素存在此时终止循环时可以直接返回 −1。left right并且查找的元素不在有序数组中则 while 语句出界条件是 left right写成区间形式就是 [ r i g h t right right, r i g h t right right]。此时区间不为空待查找区间还有一个元素存在我们并不能确定查找的元素不在这个区间中此时终止循环时如果直接返回 −1 就是错误的。
使用 left right 的话可以在出界之后增加一层判断判断是否等于目标元素。
# ...while left right:# ...return left if nums[left] target else -1此时在跳出循环的时候一定是 left right无需判断此时应该返回 left or right
搜索区间范围的选择
三种写法
left mid 1right mid - 1
left mid 1 right mid
left midright mid - 1具体哪一种写法和二分查找的两种思路有关。
思路 1「直接法」—— 在循环体中找到元素后直接返回结果。思路 2「排除法」—— 在循环体中排除目标元素一定不存在区间。
3 二分查找两种思路
3.1 直接法
设定左右边界为数组两端即 l e f t 0 r i g h t l e n ( n u m s ) − 1 left0rightlen(nums)−1 left0rightlen(nums)−1代表待查找区间为 [ l e f t , r i g h t ] [left,right] [left,right]左闭右闭区间。取两个节点中心位置 m i d mid mid 先比较中心位置值 n u m s [ m i d ] nums[mid] nums[mid] 与目标值 t a r g e t target target 的大小。 如果 t a r g e t n u m s [ m i d ] targetnums[mid] targetnums[mid]则返回中心位置。如果 t a r g e t n u m s [ m i d ] targetnums[mid] targetnums[mid] 则将左节点设置为 m i d 1 mid1 mid1然后继续在右区间 [ m i d 1 , r i g h t ] [mid1,right] [mid1,right] 搜索。如果 t a r g e t n u m s [ m i d ] targetnums[mid] targetnums[mid]则将右节点设置为 m i d − 1 mid−1 mid−1然后继续在左区间 [ l e f t , m i d − 1 ] [left,mid−1] [left,mid−1] 搜索。 如果左边界大于右边界查找范围缩小为空说明目标元素不存在此时返回 −1。
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1# 在区间 [left, right] 内查找 targetwhile left right:# 取区间中间节点mid left (right - left) // 2# 如果找到目标值则直接范围中心位置if nums[mid] target:return mid# 如果 nums[mid] 小于目标值则在 [mid 1, right] 中继续搜索elif nums[mid] target:left mid 1# 如果 nums[mid] 大于目标值则在 [left, mid - 1] 中继续搜索else:right mid - 1# 未搜索到元素返回 -1return -13.2 排除法
设定左右边界为数组两端即 l e f t 0 r i g h t l e n ( n u m s ) − 1 left0rightlen(nums)−1 left0rightlen(nums)−1代表待查找区间为 [ l e f t , r i g h t ] [left,right] [left,right]左闭右闭区间。取两个节点中心位置 m i d mid mid 比较中心位置值 n u m s [ m i d ] nums[mid] nums[mid] 与目标值 t a r g e t target target 的大小先将目标元素一定不存在的区间排除。然后在剩余区间继续查找元素继续根据条件排除目标元素一定不存在的区间。直到区间中只剩下最后一个元素然后再判断这个元素是否是目标元素。
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1# 在区间 [left, right] 内查找 targetwhile left right:# 取区间中间节点mid left (right - left) // 2# nums[mid] 小于目标值排除掉不可能区间 [left, mid]在 [mid 1, right] 中继续搜索if nums[mid] target:left mid 1 # nums[mid] 大于等于目标值目标元素可能在 [left, mid] 中在 [left, mid] 中继续搜索else:right mid# 判断区间剩余元素是否为目标元素不是则返回 -1return left if nums[left] target else -1直接法更适合解决简单题目数组中是非重复元素。排除法更适合解决复杂题目数组里可能不存在的元素找边界问题。
参考文献
[1] https://datawhalechina.github.io/leetcode-notes/#/
—— END —— 如果以上内容有任何错误或者不准确的地方欢迎在下面 留言。或者你有更好的想法欢迎一起交流学习~~~
更多精彩内容请前往 AXYZdong的博客
