简单实现: 有序数据集合中不存在重复的数据，在其中查找值等于某个给定值的数据
分治思想，每次通过跟区间的中间元素对比，将待查找的区间缩小为一半，直到找到要查找的元素，或者区间被缩小为0。
时间复杂度
时间复杂度为O(logn): 这是一种极其高效的时间复杂度，有时甚至比时间复杂度为O(1)的算法还要高效
适用场景
首先，二分查找依赖的是顺序表结构(数组) (高效按下标随机访问元素)
其次，二分查找针对的是有序数据: 二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中
再次，数据量太小不适合二分查找: 直接顺序循环即可
最后，数据量太大也不适合二分查找
二分查找底层需要依赖数组这种数据结构，数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻
变体实现
比如有序数组a[10] : 1 3 4 5 6 8 8 8 11 18，其中a[5]、a[6]、a[7]的值都等于8
变体一：查找第一个值等于给定值的元素
示例: 我们希望查找第一个等于8的数据，也就是下标是5的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
变体二：查找最后一个值等于给定值的元素
示例: 查找最后一个值等于给定值的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
变体三：查找第一个大于等于给定值的元素
示例: 数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于5的元素，那就是6
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
变体四：查找最后一个小于等于给定值的元素
示例: 数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于7的元素就是6
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
