Binary Search

Leave a comment

February 26, 2017 by oneOokay

真的是直到今天才完完全全弄明白…

参考:http://blog.csdn.net/ebowtang/article/details/50770315

首先每个人的二分法都有自己的方式来确定mid,我的习惯使用的是

mid = start + (end – start) / 2

  • 与mid = (start + end) / 2相比的优点是:
    • 当start和end为非常大的正数的时候,不会overflow. (当然优解在start和end一个为负数一个为正数的情况下会overflow)
    • 会round to start.当start = -3, end = 0的时候,直接求平均数返回的值是-1;而优解返回的是-2.更靠进start

这个的特别之处在于:

  • start + 1 == end的时候, start = mid所造成的range不变,会造成死循环
  • start == end的时候,end = mid 和 start = mid所造成的range不变,会造成死循环.

所以!!!

  • 当while loop里面存在start = mid时,循环条件为start + 1 < end. 当循环结束的时候:start + 1 == end,此时要对start和end的元素进行判断.
  • 当while loop里面存在end = mid的时候,循环条件应该为 start < end. 当循环结束的时候:start == end,此时仅对start的元素进行判断即可.

那么用二分法的步骤应该是:

  1. 先不管while loop的条件
  2. 先确定while loop之内,start = mid/mid + 1和end = mid/mid + 1.能+1的话一定要+1
  3. 根据while loop之内的start和end的移动情况来决定while loop的条件
  4. 再根据while loop的条件得知while loop结束之后start和end的情况从而对最终结果进行判断.

BinarySearch的基本应用:

  1. Find Equal
  2. Find First Equal
  3. Find Last Equal
  4. Find First Larger or Equal
  5. Find First Larger
  6. Find Last Smaller or Equal
  7. Find Last Smaller

public int findEqual(int[] A, int key){
int start = 0, end = A.length – 1;
while (start key) end = mid – 1;
else start = mid + 1; //A[mid] < key
}
return -1;
}

public int findFirstEqual(int[] A, int key){
int start = 0, end = A.length – 1;
while (start key) end = mid – 1;
else if (A[mid] < key) start = mid + 1;
else end = mid;
}
if (A[start] == key) return start;
return -1;
}

public int findLastEqual(int[] A, int key){
int start = 0, end = A.length – 1;
while (start + 1 key) end = mid – 1;
else if (A[mid] < key) start = mid + 1;
else start = mid;
}
if (A[end] == key) return end;
if (A[start] == key) return start;
return -1;
}

public int findFirstLargerEqual(int[] A, int key){
int start = 0, end = A.length – 1;
while (start = key) end = mid;
else start = mid + 1; //A[mid] = key) return start;
return -1;
}

public int findFirstLarger(int[] A, int key){
int start = 0, end = A.length – 1;
while (start < end){
int mid = start + (end – start) / 2;
if (A[mid] key) return start;
return -1;
}

public int findLastSmallerEqual(int[] A, int key){
int start = 0, end = A.length – 1;
while (start + 1 < end){
int mid = start + (end – start) / 2;
if (A[mid] <= key) start = mid;
else end = mid – 1;
}
if (A[end] <= key) return end;
if (A[start] <= key) return end;
else return -1;
}

public int findLastSmaller(int[] A, int key){
int start = 0, end = A.length – 1;
while (start + 1 = key) end = mid – 1;
else start = mid;
}
if (A[end] < key) return end;
if (A[start] < key) return start;
return -1;
}

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: