Binary Search(二分搜索)总结

数值相关的二分

67.Sqrt(x): 1 -> x的区间来二分.start=1,end=x; 最后边界条件先检查startstart<=x, 然后看endend0 return pow(x,n) 否则return 1/pow(x,Math.abs(n)); pow实现思路就是二分,if(n==0) return1;if(n==1) return x; half = pow(x,n/2);return (n % 2 == 0) ? halfhalf :halfhalf*x,
34,Search for a Range(搜索范围)/搜索duplicates: 可以两次二分查找分别找到给定target的起始点跟终止点. 注意每次二分搜索后start跟end的边界条件检查

一维数组跟二维数组里的二分搜索

  1. Search Insert Position: 给定数组是有序的,
    target array[length – 1] return length;
    array[0]nums[mid+1]) => true, if(nums[mid] <nums[mid-1]) end = mid;说明mid左边是单调递减的,应该往左边找。否则往右边找.

74.Search a 2D Matrix I: 给定的matrix中,下一行的头元素总是大于上一行的尾元素,整个二维数组中的元素是单调递增,一如何定位某一点的坐标, start=0, end= row*col-1; 某一点的表示matrix[index/col]
240.Search a 2D Matrix II: 从左下角开始 matrix[row – 1][0],往右上角搜索,如果当前点大于target就往上走,小于target就往右走

Rotated Sorted Array

153.Find Minimum in Rotated Sorted Array I: 153中不包括duplicate. 直接二分,target选最右边元素。 每次mid跟target进行比较,如果大于target,说明mid在左边逆序,最小值在右边,start=mid; 如果小于target,说明mid在右边,往左边找,end = mid; 最后再返回start跟end中较小的元素
154.Find Minimum in Rotated Sorted Array II: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;
33. Search in Rotated Sorted ArrayI:
因为rotate的缘故,当我们切取一半的时候可能会出现mid在左半边区间,或者右半边区间的情况,所以我们要做进一步的判断。假设数组是A,起始start,终止end,还有中间位置是mid。在每次迭代中,分三种情况:
A[mid] = target 找到target
A[mid] > A[start] 说明mid在左半边区间(4 5 6 7)有序的, 那么就要判断target是否在start与mid之间, 如果在的话则把m设为end边界, 否则的话target就在另外的一半, 把mid设为start边界
如果A[mid] < A[start], 说明mid在右半边区间(0 1 2 ), 那么就判断target是不是在mid到end之间.如果target在的话把mid设为start, 否则把mid设为end
最后再判断A[start],A[end]与target的关系
81. Search in Rotated Sorted ArrayII: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s