二分法查找的原理很简单，先和中间的比较，如果等于就直接返回，如果小于就在前半部分继续使用二分法进行查找，如果大于则在后半部分继续使用二分法进行查找。适用于数据量大大场景，但是要求数据有序。
public class BinarySearch {
public static int search(int[] arr,int target) {
if(arr == null || arr.length <= 0) return 0 ;
int low = 0;
int high = arr.length - 1;
while(low < high) {
int mid = (low + high) >> 1;
if(arr[mid] == target) return mid;
if(target < arr[mid]) {
high = mid - 1;
}
if(target > arr[mid]) {
low = mid + 1;
}
}
return 0;
}
}
改进版：插值查找
当我们知道要查找的数据大概在什么位置的时候，就没必要从中间找了。插值查找和普通的二分查找的区别就在于中间值的选择。
public static int insertSearch(int[] arr, int target) {
if(arr == null || arr.length <= 0) return 0 ;
int low = 0;
int high = arr.length - 1;
while(low < high) {
if(low == high) {
if(arr[low] == target) {
return low;
}
return -1;
}
int mid = low + ((target - arr[low])/(arr[high] - arr[low]))* (high - low);
if(arr[mid] == target) return mid;
if(target < arr[mid]) {
high = mid - 1;
}
if(target > arr[mid]) {
low = mid + 1;
}
}
return -1;
}
