二分思想
二分查找是一种非常容易懂的快速查找算法，生活中随处可见。比如说我们做一个猜字游戏。我随机写一个0到99之间的数字，然后你猜我写的是什么。猜的过程中，你每猜一次，我就告诉你猜的大了还是小了，直到猜中为止。
假设我写的数字是23，你可以按照以下步骤来试试。
| 次数 | 猜测范围 | 中间数 | 对比大小 |
|---|---|---|---|
| 第一次 | 0-99 | 49 | 49>23 |
| 第二次 | 0-48 | 24 | 24>23 |
| 第三次 | 0-23 | 11 | 11<23 |
| 第四次 | 12-23 | 17 | 17<23 |
| 第五次 | 18-23 | 20 | 20<23 |
| 第六次 | 21-23 | 22 | 22<23 |
| 第七次 | 23 | - | ✅ |
是不是很简单也很快速，我们用七次就猜出来了，我们用这个思想，即便猜0到999，最多也只要10次就能猜中。
二分思想： 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次通过跟中间元素的对比，将待查找的区间缩小为之前的一半，直到找到想要的元素，或者区间被缩小为零。
代码实现
public static int searchInternally(int[] a, int low, int high, int value) {
if (low > high) return -1;
int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
return searchInternally(a, mid + 1, high, value);
} else {
return searchInternally(a, low, high - 1, value);
}
}
二分查找局限性
- 二分查找依赖数组
二分查找算法需要按照下标进行随机访问，这点数组的时间复杂度最好。
- 二分查找针对的是有序数据
- 数据量太少不适合二分查找
数据量太少我们直接可以使用循环来实现，只有数据量大的适合二分的优势才能体现出来
- 数据量太大也不适合二分查找
二分查找底层需要依赖数组这种数据结构，而数组要求内存连续，对内存的要求比较苛刻，比如1GB的数据将需要1GB的连续内存空间，即便你有2GB 但是不连续的话是无法申请1GB大小的数组的。
四种二分查找变形问题
- 查找第一个值等于给定值的元素
- 查找最后一个值等于给定值的元素
- 查找第一个大于等于给定元素值元素
- 查找最后一个小于等于给定值的元素
一、查找第一个值等于给定值的元素
上面那种二分查找是最简单的一种，即数组中不存在重复的数据，我们在其中查找值等于某个人给定的值的数据。如果数组中存在相同的元素我们需要查找第一个值等于给定值的元素，按照上面的方式就不能正常的工作了。
我先给出代码：
public static int bsearch(int[] a, int n, int value) {
int low = 0, 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;
}
}
if (a[low] == value) return low;
else return -1;
}
解释一下上面的代码，a[mid]跟我们要查找的值有三种大小关系：大于，小于，等于。对于大于和小于这一块我不再说一看就明白。
重点说一下等于的情况：如果mid等于0那说明元素已经是数组中的第一个元素了，那肯定是我们要找的元素。或者a[mid]的前一个元素不等于value，那也说明a[mid]是我们要找的元素。如果这两个条件不满足的话说明a[mid]前面还有和value相同的元素，那么这个时候我们需要更新一下high的值。
二、查找最后一个值等于给定值的元素
这个问题我们只需要在上面的实现方式上稍作改动就可以实现了。
代码如下：
public static int bSearch(int[] a, int n, int value) {
int low = 0, 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;
}
我们还是重点看一下外层else中的代码，如果a[mid] 这个元素已经是数组中最后一个元素了，那它肯定是我们要找的；如果a[mid]的后一个元素a[mid+1]不等于value那也是我们要找的。如果这两个条件都不满足的话说明a[mid]后面还有和value相同的元素，那么这个时候我们需要更新一下low的值。
三、查找第一个大于等于给定元素值元素
对于这个问题实现的思路和上面的非常像，代码写起来甚至更简洁。
public static int bSearch(int[] a, int n, int value) {
int low = 0, 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;
}
四、查找最后一个小于等于给定值的元素
public static int bSearch(int[] a, int n, int value) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || a[mid + 1] > value) return mid;
else low = mid + 1;
}
}
return -1;
}
