面试必备算法：二分查找算法
算法简介
二分查找算法适用于已排序的数组。算法首先将数组中间的元素与目标值进行比较。如果目标值与元素匹配，则返回其在数组中的位置。如果目标值小于元素，则在数组的下半部分继续搜索。如果目标值大于元素，则在数组的上半部分继续搜索。通过这样做，该算法消除了每次迭代中目标值不存在的一半数据。
算法思路
给定一个有 n 个元素的数组 A ,其中元素是已经排序好的，即元素为 A1,A2A3....,An-1 ,其中 A1<=A2<=A3<=....<=An-1 ，给定要查找的目标值 T ，那么我们从数组A 中查找T的过程为：
设 L = 0，设R = n - 1;
如果 L >R, 搜索失败而结束。
设置 m 为 floor( (L+R)/2 ), 即为小于等于 (L+R)/2 ;
如果 Am < T，那么设L= m + 1，跳转到步骤2；
如果 Am > T ，那么设R = m - 1，跳转到步骤2；
Am = T，搜索结束，返回 m。
最后，根据这个思路，我们伪代码为：
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessful
其中，floor 为向下取整的函数，unsuccessful为一个特殊值代表查询失败。
如果我们对 (L + R) / 2 使用向上取整函数，并且我们查找的目标值有多个的话，返回的值可能会和上边的算法不同了。
重复元素问题
搜索过程可能返回其元素等于目标值的任何索引，即使数组中有重复的元素。例如，如果要搜索的数组是 [1,2,3,4,4,5,6,7]，并且目标是 4，那么算法返回第 4 个（索引 3）或第 5 个（索引 4）元素是正确的。在这种情况下，常规过程将返回第 4 个元素（索引 3），它并不总是返回第一个出现的元素（例如[1,2,4,4,4,5,6,7]，就会返回第四个元素）。但是，有时需要为在数组中重复的目标值找到最左边的元素或最右边的元素。在上面的例子中，第 4 个元素是值 4 的最左边元素，而第 5 个元素是值 4 的最右边元素。
查找最左侧元素
主要思路为：
设 L = 0，设 R = n;
while L < R :
设置 m 为 floor( (L+R)/2 ), 即为小于等于 (L+R)/2;
如果 Am < T ，那么设L = m + 1；
否则 Am > T ，那么设 R = m；
返回 L 。
如果L< n并且 AL=R ,那么 AL就是最左侧等于T的元素，即使T不在数组中，L也是 T在数组中的秩，或数组中小于L的元素的数量。
写成伪代码为：
function binary_search_leftmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] < T:
L := m + 1
else:
R := m
return L
查找最右侧元素
主要思路为：
设 L = 0，设 R = n;
while L < R :
设置 m 为 floor( (L+R)/2 ), 即为小于等于(L+R)/2;
如果 Am > T ，那么设 R = m；
否则 Am <= T ，那么设 L = m + 1；
返回 R - 1 。
如果R > 0 并且 A(R-1) = T,那么 A(R-1) 就是最右侧等于 T 的元素，即使T不在数组中， n - R 是数组中大于 T 的元素数。
伪代码为：
function binary_search_rightmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] > T:
R := m
else:
L := m + 1
return R - 1
Java 代码实现
public class BinarySearch<T extends Comparable<T>> {
public static int UNSECCUESSFUL = -1;
//first method
/**
* function binary_search(A, n, T) is
* L := 0
* R := n − 1
* while L ≤ R do
* m := floor((L + R) / 2)
* if A[m] < T then
* L := m + 1
* else if A[m] > T then
* R := m − 1
* else:
* return m
* return unsuccessful
* @param sortData
* @param target
* @return
*/
public int search(T[] sortData,T target) {
int len = sortData.length;
int l = 0;
int r = len - 1;
while (l <= r) {
int m = (int) Math.floor((l + r)/2);
if(sortData[m].compareTo(target) < 0) {
l = m + 1;
} else if(sortData[m].compareTo(target) > 0) {
r = m - 1;
} else {
return m;
}
}
return UNSECCUESSFUL;
}
//second method
/**
* function binary_search_leftmost(A, n, T):
* L := 0
* R := n
* while L < R:
* m := floor((L + R) / 2)
* if A[m] < T:
* L := m + 1
* else:
* R := m
* return L
* @param sortData
* @param target
* @return
*/
public int searchLeftmost(T[] sortData,T target) {
int len = sortData.length;
int l = 0;
int r = len;
while (l < r) {
int m = (int) Math.floor((l + r)/2);
if(sortData[m].compareTo(target) < 0) {
l = m + 1;
} else {
r = m;
}
}
if(l >= 0 && l < len) {
return l;
}
return UNSECCUESSFUL;
}
//third method
/**
* function binary_search_rightmost(A, n, T):
* L := 0
* R := n
* while L < R:
* m := floor((L + R) / 2)
* if A[m] > T:
* R := m
* else:
* L := m + 1
* return R - 1
* @param sortData
* @param target
* @return
*/
public int searchRightmost(T[] sortData,T target) {
int len = sortData.length;
int l = 0;
int r = len;
while (l < r) {
int m = (int) Math.floor((l + r)/2);
if(sortData[m].compareTo(target) > 0) {
r = m;
} else {
l = m + 1;
}
}
if(r - 1 >= 0 && r - 1 < len) {
return r - 1;
}
return UNSECCUESSFUL;
}
}