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

二分法及其应用文章目录二分法及其应用[toc]1.二分法2.二分法的应用1在一个有序数组中找到某个数没有返回False2在一个有序数组中找到≥某个数最左侧的位置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找到返回midarr[mid] target目标在右半区left mid 1arr[mid] target目标在左半区right mid - 1循环结束未命中则不存在返回False。defbinary_search(mylist,target):left0rightlen(mylist)-1whileleftright:midleft(right-left)//2ifmylist[mid]target:returnmidelifmylist[mid]target:leftmid1else:rightmid-1returnFalseprint(binary_search([1,2,3,3,3,5,8],2))# 结果1这是一个普通二分找到相等就跑路只求 “有没有”。2在一个有序数组中找到≥某个数最左侧的位置思路arr[mid] target记录当前位置向左搜right mid - 1arr[mid] target向右搜left mid 1若全部小于 target返回数组长度。deffindleftnumber(mylist,target):ans,left,rightlen(mylist),0,len(mylist)-1whileleftright:midleft(right-left)//2ifmylist[mid]target:ansmid rightans-1else:leftleft1returnansprint(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[i1]i ii为局部最小。要求在O ( log ⁡ n ) O(\log n)O(logn)时间找出任意一个局部最小值下标。deffindlocalmin(mylist):left,right0,len(mylist)-1ifmylist[0]mylist[1]:return0ifmylist[len(mylist)-2]mylist[len(mylist)-1]:returnlen(mylist)-1whileleftright:midleft(right-right)//2ifmylist[mid]mylist[mid1]andmylist[mid]mylist[mid-1]:returnmidelifmylist[mid]mylist[mid1]:leftmid1elifmylist[mid]mylist[mid-1]:rightmid-1returnFalseprint(findlocalmin([4,2,3,4,5,4.3,8]))# 结果1