|
第一课 binary search 1.经典二分查找 要解决的问题是：是在有序的序列中找到所需的数字。 中心思想是：将有序序列（假设为升序排列）中间的数字设为middle数值，左边第一个数字设为left，右边第一个数字设为right，将target与middle先做比较，若middle比target大，证明target应该出现在middle的左半段，则可以将middle右半段的序列舍弃，反之同理。 代码如下：
def binary_search(list1,target): if list1 == None or len(list1) == 0: return -1 left = 0 right = len(list1) - 1 while left <= right: #这里要是没有=的话，在left=right的情况下#如果target正好等于list1[left] = list1[right]就会正好被漏判，返回-1.mid = int((left+right)/2) if list1[mid] < target: left = mid + 1 elif list1[mid] > target: right = mid - 1 else: return mid return -1此算法时间复杂度为：o（logn）（假设序列长度为n） 推导：序列长度为n，比较一次后，序列长度变为n/2，比较j次过后，序列长度变为n/(2^j)，最终序列长度会变为1，所以令n/(2^j)=1，j = log2n，所以时间复杂度为o（logn）。 空间复杂度：o（1） 2.矩阵中的二分查找 问题：若给一个有序的矩阵如下所示 1 2 3 4 5 6 7 8 9 10 11 12 要在升序矩阵中查找一个目标数，利用二分查找应该怎么做？ 中心思想：把矩阵转化为一个有序序列，然后再进行二分查找。 比如，此矩阵有4行4列，1这个数字的坐标为（0,0），1在数组中的index应该为0*4+0=0。 通用公式：矩阵m行n列，数字坐标为（i，j），index = i*m+j 反之，i = index/m， j = index%m 代码如下：
#矩阵二分查找def bs(matrix,target): if matrix == None or len(matrix) == 0: return -1 row = len(matrix)#行数col = len(matrix[0])#列数left = 0 right = row*col - 1 while left <= right: mid = (left+right)//2 #转换index为matrix的坐标i = mid//row j = mid%col if matrix[j] < target: left = mid + 1 elif matrix[j] > target: right = mid - 1 else: return (i,j) return -1
时间复杂度：o（log（row*col）） 空间复杂度：o（1）
3.查找一个升序序列中离目标数最近的数字。 问题：一个升序序列中，或许并没有要找的目标数字，但是需要返回一个离目标数字最近的数字。 中心思想和问题1一致，只是要将left = mid+1和right= mid-1改为left=mid和right=mid，（因为是返回离目标数最近的数字，所以mid即使和target不一样也需要留下来判断是否离target近）。但是如果使用问题1的代码，会出现死循环问题。比如在[1,2,5]中寻找离3最近的数字时，到最后会出现left=right=1，那么target永远> mid[left+right//2]，程序会一直死循环下去。宏观来说就是left=right=mid时，mid又不等于target，left和right就会因为left=mid或者right=mid以及mid= （left+right）//2的语句一直卡在left=right=mid这里。为了解决这个问题，需要把代码中while的条件放宽为left<right-1,让left永远不等于right就不会出现死循环问题。最后在代码最后加一个判断。 代码如下：
def closeted(list1,target): if list1==None or len(list1)==0: return -1 left = 0 right = len(list1)-1 while left < right - 1: mid = (left+right)//2 if list1[mid] > target: right = mid elif list1[mid] < target: left = mid else: return mid return left if abs(list1[left]-target) < abs(list1[right]-target) else right时间复杂度：o（logn）
4.如果升序序列中有重复的数值出现，比如[1,2,2,3,4]，查找最早或者最后出现的2。 中心思想是在问题3的基础上加以变动，二分搜索到最后left=right-1之后，判断left和right是否等于target，查找最早出现就先判断left是否=target，查找最后出现就先判断right是否等于target。但是在判断的时候还是有点细微差别。具体见代码。 代码如下：
#寻找最后出现的targetdef last(list1,target): if len(list1) == 0 or list1 == None: return 1 left = 0 right = len(list1) - 1 while left < right - 1: mid = (left + right)//2#第一条判断语句，在判断最后出现的target时，需要先确定可能重复的target在哪个区间，比如先判断序列的左半段有没有重复的target，以免漏判。 if list1[mid] > target: right = mid else: left = mid if list1[right] == target: return right if list1[left] == target: return left return -1寻找最先出现的target时也需要先判断可能重复的target没有在右半段出现。 时间复杂度：o（logn） 5，寻找peak值 问题：找一个序列中，比旁边两个数都大的那个数（peak）。 中心思想：利用二分查找，设置一个mid。 if array[mid] > array[mid-1] and array[mid] > array[mid+1]: return mid if array[mid] < array[mid+1]:证明peak出现在mid的右半段，left=mid+1 if array[mid] < array[mid-1]:证明peak出现在mid的左半段，right = mid-1 代码如下：
def peakpick(nums): if nums == None or len(nums) == 0: return -1 left = 0 right = len(nums) - 1 while left < right - 1: mid = (left+right)//2 if nums[mid] > nums[mid+1] and nums[mid]>nums[mid-1]: return mid if nums[mid] < nums[mid+1]: left = mid+1 if nums[mid] < nums[mid-1]: right = mid-1 return left if nums[left]>=nums[right] else right这段代码只能查找出一个peak值，另外的就无法查找得出。 最后一句代码的原因是在程序最后已经查找到序列最边边了，只用查找到最大值即可。 6.在旋转序列中利用二分查找查找target。 旋转序列：类似于 3,4,5,0,1,2。这样的序列。
![]()
将345分为区间1，将012分为区间2。利用二分查找。 如果array[left] < array[mid]那么array[mid]落在区间1，如果array[left]<=target<array[mid],那么就在区间一进行搜索。反之在区间2进行搜索。 if array[mid]<array[left],那么mid落在区间2, 如果array[mid]<target<array[right]，就在区间2中进行搜索，反之在区间1进行搜索。
def r(array,target): if array == None or len(array)==0: return -1 left = 0 right = len(array)-1 while left <= right: mid = (left+right)//2 if array[mid] == target: return mid if array[mid] >= array[left]:#mid落在一区间if array[mid] > target and target > array[left]: right = mid - 1 else: left = mid + 1 else: if array[mid] < target and target < array[right]: left = mid + 1 else: right = mid - 1 return -1
| 
收藏
淘帖
踩
