在《編程珠璣》中有詳細的討論。主要出于性能方向改進。
- 二分法很簡單吧 ,但要想 一次寫對 也不容易吧 ,更何況他的一些擴展應用呢 ,我這里擴展了四種,<P> </P><P>基礎知識 還是牢靠的好</P><P> </P>
- /**
- * 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));
- }
- }