【算法与数据结构】二分法及其应用
二分法及其应用
文章目录
- 二分法及其应用
- @[toc]
- 1.二分法
- 2.二分法的应用
- （1）在一个有序数组中，找到某个数，没有返回False
- （2）在一个有序数组中，找到≥某个数最左侧的位置
- （3）局部最小值问题（无序数组二分）
文章目录
- 二分法及其应用
- @[toc]
- 1.二分法
- 2.二分法的应用
- （1）在一个有序数组中，找到某个数，没有返回False
- （2）在一个有序数组中，找到≥某个数最左侧的位置
- （3）局部最小值问题（无序数组二分）
1.二分法
二分法适核心逻辑是不断取中间值缩小搜索范围，时间复杂度O ( log n ) O(\log n)O(logn)，远优于遍历算法复杂度O ( n ) O(n)O(n)。
2.二分法的应用
（1）在一个有序数组中，找到某个数，没有返回False
思路：
升序数组，左边界left、右边界right，取中点mid比较：
arr[mid] == target：找到，返回mid；arr[mid] < target：目标在右半区，left = mid + 1；arr[mid] > target：目标在左半区，right = mid - 1；- 循环结束未命中则不存在，返回
False。
defbinary_search(mylist,target):left=0right=len(mylist)-1whileleft<=right:mid=left+(right-left)//2ifmylist[mid]==target:returnmidelifmylist[mid]<target:left=mid+1else:right=mid-1returnFalseprint(binary_search([1,2,3,3,3,5,8],2))# 结果：1这是一个普通二分，找到相等就跑路，只求 “有没有”。
（2）在一个有序数组中，找到≥某个数最左侧的位置
思路：
arr[mid] >= target：记录当前位置，向左搜，right = mid - 1；arr[mid] < target：向右搜，left = mid + 1；- 若全部小于 target，返回数组长度。
deffindleftnumber(mylist,target):ans,left,right=len(mylist),0,len(mylist)-1whileleft<=right:mid=left+(right-left)//2ifmylist[mid]>=target:ans=mid right=ans-1else:left=left+1returnansprint(findleftnumber([1,2,3,3,3,5,8],2))# 结果：1print(findleftnumber([1,2,3,3,3,5,8],100))# 结果：7（没找到就会返回初始化时候标定的mylist的长度）这是一个左边界二分，相当于满足条件的先记下来，继续往左找，只求最左边那一个。
（3）局部最小值问题（无序数组二分）
问题描述：
给定数组，相邻元素不相等，定义局部最小：
若
arr[0] < arr[1]：0 号位置是局部最小；若
arr[n-1] < arr[n-2]：末尾是局部最小；中间位置i ii满足
arr[i]<arr[i-1] and arr[i]<arr[i+1]：i ii为局部最小。要求：在O ( log n ) O(\log n)O(logn)时间找出任意一个局部最小值下标。
deffindlocalmin(mylist):left,right=0,len(mylist)-1ifmylist[0]<mylist[1]:return0ifmylist[len(mylist)-2]>mylist[len(mylist)-1]:returnlen(mylist)-1whileleft<=right:mid=left+(right-right)//2ifmylist[mid]<mylist[mid+1]andmylist[mid]<mylist[mid-1]:returnmidelifmylist[mid]>mylist[mid+1]:left=mid+1elifmylist[mid]<mylist[mid-1]:right=mid-1returnFalseprint(findlocalmin([4,2,3,4,5,4.3,8]))# 结果：1