【算法与数据结构】二分法及其应用

二分法及其应用

文章目录

• • • 二分法及其应用
  • @[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）局部最小值问题（无序数组二分）

问题描述：

给定数组，相邻元素不相等，定义局部最小：

1. 若arr[0] < arr[1]：0 号位置是局部最小；

2. 若arr[n-1] < arr[n-2]：末尾是局部最小；

3. 中间位置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