算法原理

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。如果插入排序涉及到较大数据量，可应用到插入排序中。

代码实现

  1. public void testBinarySearch() {
  2.         int[] data = {1,2,3,4,5,6,7,7,8};
  3.         int index = binarySearchWithRecursive(data, 0, data.length - 1, 7);
  4.         if (index == -1) {
  5.             System.out.println("Not Found");
  6.         } else {
  7.             System.out.println("Binary Search Result: " + data[index]);
  8.         }
  9.         index = binarySearchWithWhileLoop(data, 0, data.length, 8);
  10.         System.out.println("WhileLoop Search: " + data[index]);
  11.  }
  12. public static int binarySearchWithRecursive(int[] array, int start, int end, int key) {
  13.         if (start > end) {
  14.             return -1;
  15.         }
  16.         int mid  = (start + end) / 2;
  17.         if (array[mid] == key) {
  18.             return mid;
  19.         }
  20.         if (array[mid] < key) {
  21.             return binarySearchWithRecursive(array, mid + 1, end, key);
  22.         }
  23.         return binarySearchWithRecursive(array, start, mid - 1, key);
  24.  }
  25. public static int binarySearchWithWhileLoop(int[] array, int start, int end, int key) {
  26.         int index = -1;
  27.         while (start <= end) {
  28.             int mid = (start + end) / 2;
  29.             if (array[mid] == key) {
  30.                 return mid;
  31.             }
  32.             if (array[mid] < key) {
  33.                 start = mid + 1;
  34.             } else {
  35.                 end = mid - 1;
  36.             }
  37.         }
  38.         return index;
  39.  }

循环版

  1. public static int loopFind(int[] data, int start, int end, int target) {
  2.     while (start <= end) {
  3.         int mid = (start + end) / 2;
  4.         if (data[mid] == target) {
  5.             return mid;
  6.         }
  7.         if (data[mid] < target) {
  8.             start = mid + 1;
  9.         } else {
  10.             end = mid - 1;
  11.         }
  12.     }
  13.     return -1;
  14. }

递归

  1. public static int recurFind(int[] data, int start, int end, int target) {
  2.     if (start > end) {
  3.         return -1;
  4.     }
  5.     int mid = (start + end) / 2;
  6.     if (data[mid] == target) {
  7.         return mid;
  8.     }
  9.     if (data[mid] < target) {
  10.         return recurFind(data, mid + 1, end, target);
  11.     }
  12.     return recurFind(data, start, mid - 1, target);
  13. }

测试代码

  1. @Test
  2. public void testBS() {
  3.     int[] data = {1, 2, 3, 4, 5, 6, 7};
  4.     System.out.println(loopFind(data, 0, data.length, 0));
  5.     System.out.println(recurFind(data, 0, data.length, 0));
  6. }