二分查找法(折半查找法)
一、算法介绍
二分查找法：也称折半查找法，是一种效率较高的查找方法，存在一定的局限性。
局限性：适用于有序数组、有序链表等查找，例如：Array，List。
二、算法原理
基本原理：
第一步：设定需要查找的元素key，再设定low和high两个临时指针分别指向左边第一个元素和右边最后一个元素。
第二步：因为数据是有序的，先根据low和high计算出数据的中位数mid，把数据分割成左右两部分，左边部分数据都是小于中位数，右边部分数据都是大于中位数的。
第三步：判断key是大于还是小于mid。如果key>mid，先移动low指针到（mid+1）的位置，再根据low和high重新计算中位数。如果key<mid，先移动high指针到（mid-1）的位置，再根据low和high重新计算中位数。如果key=mid，直接返回key的元素下标。
第四步：不断重复比较key和mid的大小，再移动low或high指针，重新计算数据的中位数，直到查找到key或循环停止。
算法步骤图解：
源数据为：int[] nums = {1, 2, 3, 4, 6, 7, 10, 12};
第一步：设定key=10、左指针low=0、右指针high=（nums.length-1）=7。
第二步：根据low=0和high=7计算数据的中位数mid=3，中位数值为nums[3]=4，再比较key和中位数的大小。
第三步：判断10>4、把low移动到（mid+1）的位置。再根据low=4和high=7计算数据的中位数mid=5，中位数值为num[5]=7，再比较key和中位数的大小。
第四步：判断10>7，把low移动到（mid+1）的位置。再根据low=6和high=7计算数据的中位数mid=6，中位数值为nums[6]=10，再比较key和中位数的大小。
第五步：判断10=10，说明查找到元素了，直接终止计算并返回元素下标。
中位数计算方式：
方式一：int mid = (low+high)/2; // (low+high)可能会超过int的最大值，导致整型溢出。
方式二：int mid = low + ((high-low)>>1); // 也可能出现问题。
方式三：int mid = (low+high)>>>1; // 得到左中位数，推荐写法。
方式四：int mid = (low+high+1)>>>1; // 得到右中位数，推荐写法。
三、算法源码
/**
* 二分法查找(折半查找法)
* @param nums
* @param key
* @return
*/
public static int binarySearch(int[] nums, int key) {
if (nums == null) {
return -1;
}
int low = 0; // 起始位置
int high = nums.length-1; // 结束位置
while (low <= high) {
int mid = (low + high) >>> 1; // 得到左中位数,推荐写法
if (nums[mid] < key) { // key>mid, 把左指针往右移动
low = mid + 1;
} else if (nums[mid] > key) { // key<mid, 把右指针往左移动
high = mid - 1;
} else {
return mid; // 查找到元素, 返回
}
}
return -1;
}
博学之，审问之，慎思之，明辨之，笃行之。
--《中庸》