在介绍实现之前需要先来说一下二分法查找的定义，以及一些前置条件。
前提
数组必须是有序的
算法描述
- 有一个有序数组 A
- 定义算法的左右边界，分别为 L 和 R， 循环执行二分查找。
- 获取中间索引 M = (L R) / 2
- 中间索引的值与待查找的值 T 进行比较
- 中间索引的值 A[M] 与带查找的值 T 进行比较 4.1 A[M] = T 表示找到，返回中间索引 4.2 A[M] > T 中间值右侧的其它元素都大于 T， 无需比较，去中间索引左边去找，M-1 设置为右边界，重新查找 4.3 A[M] < T 中间值左侧的其它元素都小于 T， 无需比较，去中间索引右边去找，M-1 设置为左边界，重新查找
- 当 L > R 时，表示没有找到，应结束循环
算法实现
根据上面的描述，我们可以轻松的实现一版实现，如下所示：
代码语言：javascript复制 private static int binarySearch(int[] arr, int target){
int left = 0, right = arr.length - 1, mid;
while (left <= right) {
mid = (left right) / 2;
if(arr[mid] == target) {
return mid;
} else if(arr[mid] > target) {
right = mid - 1;
} else if(arr[mid] < target) {
left = mid 1;
}
}
return -1;
}上面这一版实现看起来是那么的清爽，干净，但是可能会有一些 bug
注意事项
mid = (left right) / 2; 这一行代码可能就会出现溢出问题，举个例子就明白了，假设数组的长度是 int 的最大值，target 在数组中间靠右的位置，那么第一次计算 mid 是不会有问题，再次进入 while 循环的时候，此时 left = mid 1, 然后再计算 left right 就会出现溢出问题了。
怎么解决这种问题呢？大家可能经常看着这种写法 left (right - left) / 2 , 这确实可以解决问题，公式的推导过程我这里也写出来(我最开始看到这种写法惊呆了)。
代码语言：javascript复制(left right) / 2 ⇒
left / 2 right / 2 ⇒
left (-left / 2 right / 2) ⇒
left (right - left) / 2如果只有这种解决我还写什么呢？我主要是想介绍如下一种解决方法，使用无符号右移 1 位来表示除以 2。(left right) >>> 1 这么写也能达到除以 2 的要求，而且更简洁，效率更高。
好了，最后在给大家贴一下完整的优雅的二分法的实现，欢迎大家拍砖讨论哈。
代码语言：javascript复制 private static int binarySearch(int[] arr, int target){
int left = 0, right = arr.length - 1, mid;
while (left <= right) {
mid = (left right) >>> 1;
if(arr[mid] == target) {
return mid;
} else if(arr[mid] > target) {
right = mid - 1;
} else if(arr[mid] < target) {
left = mid 1;
}
}
return -1;
}
