二分查找算法 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);
}
}