前言：
二分查找又称折半查找，是一种效率较高的查找方法。前提条件：列表为有序 ， 时间复杂度：o(logn)。
算法原理：
<1>首先确定为查找区间的中间位置mid = (end - start) / 2 + start；
<2>比较中间位置与目标元素的值：
1)若相等，则查找成功，返回结束；
2)若中间位置元素大于目标值，则在中间位置左半部分查找；
3)若中间位置元素小于目标值，则在中间位置右半部分查找；
<3>重复上述步骤。
算法实现：
/**
* @author lm
* @create 2018-10-13 13:11
* @desc 折半查找算法
**/
public class BinarySearch {
/**
* 折半查找算法
*
* @param arr 有序数组
* @param start 数组起始 查找位置
* @param end 数组结束查找位置
* @param target 目标元素
* @return -1：查找失败 非-1: 元素所在位置
*/
public static int binarySearch(int[] arr, int start, int end, int target) {
if (start >= end) {
return -1;
}
int mid = (end - start) / 2 + start;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
end = mid - 1;
return binarySearch(arr, start, end, target);
} else {
start = mid + 1;
return binarySearch(arr, start, end, target);
}
}
//测试用例
public static void main(String[] args) {
int[] arr = {0,1,2,3,4,5,6,7,8,9,10};
int res = binarySearch(arr,0, arr.length, 5);
System.out.println(res);
}
}
算法分析：
<1>由于每次折半查找，因此查找次数比较少，查找速度相对较快，平均性能比较好；
<2>由于要求带查找列表为有序，因此该算法适用于元素不经常变动而查找频繁的场景。
