二分查找算法 Java

提到查找算法，最經典的就是二分查找算法了。在二分查找時要在有序的數據裡查找目標target，先取中間元素與target比較，當target小於中間元素的時候，則搜索數組的前半部分，target大於中間元素時，則取數組的後半部分。重復整個搜索的過程將左半部分與有半部分當作子數組繼續查找，直到找到元素或到子數組的大小為0停止。

原理上很簡單卻有較多細節,尤其是數據邊界的取值是否會越界，while循環的條件。

Golang二分查找算法的簡單實現 http://www.linuxidc.com/Linux/2014-02/96093.htm

二分查找改進版 http://www.linuxidc.com/Linux/2013-10/91721.htm

二分查找的實現及注意事項 http://www.linuxidc.com/Linux/2013-07/87308.htm

用Python實現二分查找 http://www.linuxidc.com/Linux/2012-12/75948.htm

二分查找之Java實現 http://www.linuxidc.com/Linux/2012-05/59869.htm

Java針對數組的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm

Java code:

public class BinarySearchDemo {
 private int search1(int[] a, int target) {
  int left = 0;
  int right = a.length - 1;
  int mid;
  while (left <= right) {
   mid = left + ((right - left) >> 1);
   if (a[mid] < target) {
    left = mid + 1;
   } else if (a[mid] > target) {
    right = mid - 1;
   } else
    return mid;
  }
  return -1;
 }

 public int search2(int[] a, int target) {
  int left = 0;
  int right = a.length;// 這裡取數組大小對後面while循環有影響
  int mid;
  while (left < right) {
   mid = left + ((right - left) >> 1);
   if (target < a[mid])
    right = mid;
   else if (target > a[mid])
    left = mid + 1;
   else
    return mid;
  }
  return -1;
 }

 // 二分法的遞歸實現
 public int search3(int[] a, int left, int right, int target) {
  if (left > right)
   return -1;
  int mid = left + ((right - left) >> 1);
  if (a[mid] < target) {
   return search3(a, mid + 1, right, target);
  } else if (a[mid] > target) {
   return search3(a, left, right - 1, target);
  } else {
   return mid;
  }
 }

 public static void main(String[] args) {
  int a[] = { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11 };
  int target = 11;
  BinarySearchDemo bs = new BinarySearchDemo();
  int pos1 = bs.search1(a, target);
  System.out.println("search1:" + pos1);
  int pos2 = bs.search2(a, target);
  System.out.println("search2:" + pos2);
  int pos3 = bs.search3(a, 0, a.length, target);
  System.out.println("search3:" + pos3);
 }
}