#Binary search#

Leave a comment

September 29, 2016 by oneOokay

二分法???换键盘,这个键盘敲得我手指头疼=。=

基本的模板是:

  • int start = 0;
  • int end;
  • while (start + 1 < end) {
  • int mid = start + (end – start) / 2;
  • if (mid == target) { }
  • if (mid > target) { end = mid;}
  • else { start = mid; } // mid < target
  • }
  • 根据情况对start和end的值进行判断

相关的题目有:

  • Classic Binary Search: 没什么特别的,最基础的。
  • Search Insert position: 最基本的binary search的实现
  • Search a 2D Matrix: 每行每列严格递增,且每列第一个元素都大于前一列的最后一个元素。把2维matrix当做一个一维的array来处理 m[mid / col][mid % col]
  • First position of target: 存在重复的数组,若target存在,找到第一个出现的index
    • 当nums[mid] == target的时候,要把end = mid。同时在最后先对start进行判断。
  • First Bad Version: 和first position of target一样的。
  • Last position of target: 存在重复的数组,若target存在,找到最后一个出现的index
    • 当num[mid] == target的时候,要把start = mid。同时在最后先对end进行判断。
  • Closest Number in Sorted Array: 也没什么特别的,while-loop完成之后,用Math.abs()对start-target和end-target进行判断。
  • *K Closet Number in Sorted Array: 找到开始的index,然后一个for-loop
  • Search in a Big Sorted Array: 找到一个比target大的数,然后进行binary search。
  • Total Occurrence of Target: First position of target 与 Last position of target的结合,找出这两个的index,然后last – first + 1则为occurrence,否则为0.
  • Search for a Range: 同Total Occurrence of Target.
  • *Wood Cut:找出最小能cut的长度为1,最大为最长木头的长度,当cut长度为mid时候,能够cut出来的木头数量如果大于k,则说明cut的长度偏小,可以cut长一点,于是把start = mid;如果cut出来的木头数量小于k,则说明cut的长度偏长,可以cut短一点,于是把end = mid。如此转换成了一个binary search 的问题。
  • *Find Minimum in Rotated Sorted Array I: 无重复值。是一个变体的binary search,把中点和起点和终点进行比较。注意其实也有可能没有rotate,需要把这个考虑到。
  • *Find Minimum in Rotated Sorted Array II:含重复值。 有最坏情况是只有一个值不一样,其他都一样。可以直接用for-loop,或者用binary search的话,mid跟end比,当相等时,end–。
  • *Search In Rotated Sorted Array I:无重复值。主要是有逻辑的划分好区间。首先判定mid是在左上升区间还是右上升区间,然后当前情况下的单调增区间,当target位于该区间时,能够确定是把mid给start还是end,然后else就为另外的一种情况了。
  • Search In Rotated Sorted Array II: 有重复值。同Find Minimum in Rotated Sorted ArrayII的情况。结合Find Minimum in Rotated Sorted ArrayII 和Search In Rotated Sorted ArrayI来结就很简单。
  • *Find Peak Element: 注意审题,起点递增,终点递减。二分法的时候,将mid与mid+1和mid-1相比。

不适用binary search:

  • *Search a 2D Matrix II: 每行每列严格递增,但每列第一个元素不一定大于前一列的最后一个元素。不是单调递增,而是从一个点开始以矩阵的范围辐射扩散增加。所以选取右上角或左下角作为起点进行判断,row–/++ col — /++, 之后逐渐缩小范围进行判断。
    • 右上角:比它大的数都一定在它的下方,比它小的数都一定在它的左边;
    • 左下角:比它大的数都一定在它的右边,比它小的数都一定在它的上方;
    • 左上角:比它大的数可能在它的下方或者右边。不能够进行规律的缩小范围,排除。
    • 右下角:比它小的数可能在它的左边或者上方。不能够进行规律的缩小范围,排除。
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0] == null) {
return false;
}
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] > target){
col --;
}else if (matrix[row][col] < target) {
row ++;
}else {
return true;
}
}
return false;
}

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

%d bloggers like this: