二分查找法也称为折半查找法，在有序的序列中使用二分法可以提高程序的执行效率。
典型的二分查找法代码
public int binarySearch1(int[] arr,int target){
int l = 0, r = arr.length - 1; // 在区间[l..r]的范围中寻找target
while(l <= r){ // 当l == r时，区间[l..r]依然是有效的
int mid = l + (r - l)/2; // 等价于(l + r) / 2，因为l + r 可能会产生整型溢出问题
if(target == arr[mid]){
return mid;
}
if (target > arr[mid]) {
l = mid + 1; // target在[mid + 1,r]中
}else{ // target < arr[mid]
r = mid - 1; // target在[l,mid - 1]中
}
}
return -1; // 没有target返回-1
}
也可以写成这样
public int binarySearch12(int[] arr,int target){
int l = 0, r = arr.length; // 在区间[l..r)的范围中寻找target
while(l < r){ // 当l == r时，区间[l..r)依然是有效的
int mid = l + (r - l)/2;
if(target == arr[mid]){
return mid;
}
if (target > arr[mid]) {
l = mid + 1; // target在[mid + 1,r]中
}else{ // target < arr[mid]
r = mid; // target在[l,mid)中
}
}
return -1; // 没有target返回-1
}