與心靈對話

二分法很簡單吧 ，但要想 一次寫對  也不容易吧 ，更何況他的一些擴展應用呢 ，我這里擴展了四種，
 
基礎知識 還是牢靠的好
 

/**
* Author: yiminghe
* Date: 2008-10-13
* Time: 23:50:48
* Any problem ,contact yiminghe@fudan.edu.cn.
*/
public class BinarySearch {
//返回中間一個數
//12345666689
// 6  不確定返回哪個6
public static int b1(int[] array, int v) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (array[middle] == v) return middle;
if (array[middle] > v)
right = middle - 1;
else
left = middle + 1;
}
return -1;
}
//返回重復元素的最后一個數
//123456667
//最后一個6位置返回
public static int b2(int[] array, int v) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int middle = (left + right + 1) / 2;
if (array[middle] > v)
right = middle - 1;
else
left = middle;
}
if (array[left] == v)
return left;
return -1;
}
//返回重復元素的最前一個數
//123456667
//最前一個6位置返回
public static int b3(int[] array, int v) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int middle = (left + right) / 2;
if (array[middle] < v)
left = middle + 1;
else
right = middle;
}
if (array[right] == v)
return right;
return -1;
}
//返回重復元素的最前一個數
//1234566689
//最前一個6位置返回 ,若找不到，顯示 比他小的離它最大位置，比它小的離它最小位置
//如 找 7 ，則 輸出 最后一個6的位置 和 8 的位置
public static int b4(int[] array, int v, int flag) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int middle = (left + right) / 2;
if (array[middle] < v)
left = middle + 1;
else
right = middle;
}
if (array[right] == v)
return right;
System.out.println(right - 1 + "  -- " + left);
return -1;
}
public static void main(String[] args) {
//                       0, 1, 2, 3  4  5  6  7
int[] array = new int[]{1, 2, 3, 4, 10, 16, 16, 16, 16, 16, 16, 18, 110};
//array = new int[]{0, 6};
//array = new int[]{6, 7};
System.out.println(b1(array, 16));
System.out.println(b2(array, 16));
System.out.println(b3(array, 16));
System.out.println(b4(array, 6, 1));
}
}