二分查找算法 Java

提到查找算法，最经典的就是二分查找算法了。在二分查找时要在有序的数据里查找目标target，先取中间元素与target比较，当target小于中间元素的时候，则搜索数组的前半部分，target大于中间元素时，则取数组的后半部分。重复整个搜索的过程将左半部分与有半部分当作子数组继续查找，直到找到元素或到子数组的大小为0停止。

原理上很简单却有较多细节,尤其是数据边界的取值是否会越界，while循环的条件。

Golang二分查找算法的简单实现

二分查找改进版

二分查找的实现及注意事项

用Python实现二分查找

二分查找之Java实现

Java针对数组的普通查找法和二分查找法

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);
 }
}