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

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

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