学习资源：慕课网liuyubobobo老师的《算法与数据结构精解》
1、简介
二分查找算法（binary search algorithm），也称折半搜索算法（half-interval search algorithm）、对数搜索算法（logarithmic search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。
算法描述：
- 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束
- 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较
- 重复步骤2，直到找到；或者在某次第2步后数组为空，则代表找不到。
二分搜索只对有序数组有效；这种搜索算法每一次比较都使搜索范围缩小一半。
由Tushe2000 - Template:LoStrangolatore，公有领域，链接
2、代码实现
算法功能：二分查找法，在有序数组 arr 中，查找 target ，如果找到 target ，返回相应的索引 index ；如果没有找到 target ，返回 -1 。
2.1、循环法
// 非递归的二分查找算法
public class BinarySearch {
// 算法类不允许产生任何实例
private BinarySearch() {}
public static int find(Comparable[] arr, Comparable target) {
// 在arr[l...r]之中查找target
int l = 0, r = arr.length-1;
while( l <= r ){
//int mid = (l + r)/2;
// 防止极端情况下的整形溢出，使用下面的逻辑求出mid
int mid = l + (r-l)/2;
if( arr[mid].compareTo(target) == 0 )
return mid;
if( arr[mid].compareTo(target) > 0 )
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
}
2.2、递归法
// 递归的二分查找算法
public class BinarySearch2 {
// 我们的算法类不允许产生任何实例
private BinarySearch2() {}
private static int find(Comparable[] arr, int l, int r, Comparable target){
if( l > r )
return -1;
int mid = l + (r-l)/2;
if( arr[mid].compareTo(target) == 0 )
return mid;
else if( arr[mid].compareTo(target) > 0 )
return find(arr, l, mid-1, target);
else
return find(arr, mid+1, r, target);
}
public static int find(Comparable[] arr, Comparable target) {
return find(arr, 0, arr.length-1, target);
}
}
3、复杂度分析
时间复杂度：折半搜索每次把搜索区域减少一半，时间复杂度为 O(logn) 。（n代表集合中元素的个数）
空间复杂度： O(1) 。虽以递归形式定义，但是尾递归，可改写为循环。
| 复杂度 | |
|---|---|
| 平均时间复杂度 | O(logn) |
| 最坏时间复杂度 | O(logn) |
| 最优时间复杂度 | O(1) |
| 空间复杂度 | 迭代： O(1) 递归：O(logn)（无尾调用消除） |
| 最佳解 | Yes |