二分查找
1、二分查找针对的是一个有序集合，查找思想主要采用分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素。要查找的元素比中间的元素小，则将范围缩小为集合的前半部分，如果待查找的元素比中间的元素大，则将将范围缩小为集合的后半部分，然后重复这个过程，直到找到元素的下标为止。
2、二分查找的时间复杂度：O(logn)
3、二分查找的局限性：
(1)二分查找依赖的是顺序表结构，简单点说就是数组
(2)二分查找针对的是有序数据,也就是说集合排好序后，才能使用二分查找
(3)数据量太小不适合二分查找，数量小的话，直接遍历就可以，可不用二分查找。
(4)数据量太大也不适合二分查找，由于依赖于顺序表结构，这里以数组为例，数组在存储结构上是逻辑连续的，数据量很大，意味着需要申请很大的连续的内存空间，这就导致很大的局限性。
代码实现
public class BinarySearch {
/**
* 二分查找迭代算法
*
* @param arr 数组
* @param len 长度
* @param value 要找的值
* @return
*/
public static int binarySearch(int[] arr, int len, int value) {
if (arr == null) {
return -1;
}
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
}
/**
* 二分查找-递归
*
* @param arr 数组
* @param len 长度
* @param value 要找的值
* @return
*/
public static int binarySearchRecursion(int[] arr, int len, int value) {
if (arr == null) {
return -1;
}
return bsBinarySearch(arr, 0, len - 1, value);
}
public static int bsBinarySearch(int[] arr, int low, int high, int value) {
if (low > high) {
return -1;
}
int mid = (low + high) >> 1;
if (arr[mid] > value) {
return bsBinarySearch(arr, low, mid - 1, value);
} else if (arr[mid] < value) {
return bsBinarySearch(arr, mid + 1, high, value);
} else {
return mid;
}
}
/**
* 变体一：查找第一个值等于给定值的元素
*/
public static int binarySearch1(int[] arr, int len, int value) {
if (arr == null) {
return -1;
}
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
if (mid == 0 || arr[mid - 1] != value) {
return mid;
} else {
high = mid - 1;
}
}
}
return -1;
}
/**
* 变体二：查找最后一个值等于给定值的元素
*/
public static int binarySearch2(int[] arr, int len, int value) {
if (arr == null) {
return -1;
}
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
if (mid == len - 1 || arr[mid + 1] != value) {
return mid;
} else {
low = mid + 1;
}
}
}
return -1;
}
/**
* 变体三：查找第一个大于等于给定值的元素
*/
public static int binarySearch3(int[] arr, int len, int value) {
if (arr == null) {
return -1;
}
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] >= value) {
if (mid == 0 || arr[mid - 1] < value) {
return mid;
} else {
high = mid - 1;
}
} else {
low = mid + 1;
}
}
return -1;
}
/**
* 变体四：查找最后一个小于等于给定值的元素
*/
public static int binarySearch4(int[] arr, int len, int value) {
if (arr == null) {
return -1;
}
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > value) {
high = mid - 1;
} else {
if (mid == len - 1 || arr[mid + 1] > value) {
return mid;
} else {
low = mid + 1;
}
}
}
return -1;
}
}
