二分法搜索初步总结
文章目录
什么是二分查找
二分查找是计算机科学中最基本、最有用的算法之一。 它描述了在有序集合中搜索特定值的过程。
在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。
关键变量
在二分查找中，有几个变量是我们着重关注的：
- 目标值（target）:即根据题目要求我们想要定位到的值。
- 索引（index）：即当前循环指定到的位置。
- 左右边界的值（low，high）：我们用来维持查找空间的值。
- 中间指示符（mid）：我们用来应用条件来确定应该向左或者向右查找的索引。
四个模板
二分搜索的思路其实很简单，但是有一句用来形容二分搜索的话是“思路很简单，细节是魔鬼”，二分法对于几个变量的控制上会因为细小的区别而对应不同的模板，这里根据做题经验和别的总结找到四种模板。
- 基础模板，直接定位target值。
- 定位target的左边界值/查找元素及其右邻居的值。
- 定位target的右边界值/查找元素及其左邻居的值。
- 查找元素的左右邻居的值。
接下来将对这四种模板进行分析和举例。
模板一
模板一也就是最基本的二分搜索的模板，是二分法最基础的模板，有了这个基础模板的掌握，也就会更好地理解剩下的三个模板。
代码
//基础模板
public static int find1(int[] nums,int target){
if(nums == null || nums.length == 0)
return -1;
int low = 0;
int high = nums.length-1;
int mid;
while(low<=high){
mid = low+((high-low)>>1);
if(nums[mid] == target)
return mid;
else if(nums[mid]>target){
high = mid-1;
}else {
low = mid+1;
}
}
return -1;
}
关键属性
- 二分查找最基本的形式。
- 查找条件可以在不与元素的两侧进行比较的情况下确定。（或者使用它周围的元素）
- 不需要后处理，因为在每一步中，都在检测是否找到了元素。如果到达末尾，则知道未找到该元素。
区分语法
- 初始条件：low = 0；high = nums.length-1；
- 终止：low>high
- 向左查找：high = mid-1;
- 向右查找：low = mid+1;
例题
class Solution {
public int search(int[] nums, int target) {
int low = 0;
int high = nums.length-1;
int mid;
while(low<=high){
mid = low+((high-low)>>1);
if(nums[mid] == target)
return mid;
if(nums[mid]>target){
if(target<=nums[high] && nums[mid]>nums[high]){
low = mid + 1;
}else{
high = mid -1;
}
}else {
if(target>=nums[low] && nums[mid]<nums[low]){
high = mid - 1;
}else{
low = mid + 1;
}
}
}
return -1;
}
}
说明：对于该题，按照查找元素的边界条件来看，使用的是基础模板，但是由于数组是旋转之后的状态，所以数组将被分为两个升序的部分。所以每进行一次查找，都需要判断当前元素在哪一个升序的部分然后确定下一个查找的空间。因为题目中提到了假设数组中不存在相同的元素，所以不需要考虑元素相邻的元素的值，找到元素可以直接返回mid值，循环结束如果没有找到即返回-1。
ps：如果假设数组中可能存在重复元素呢？
现在将题目要求变成：如果数组中存在多个相同的元素，要求返回最小的那个索引值。
分析：
如果数组中存在多个重复的元素，可能会出现这种比较烦人的测试用例：
int arr[] = {1,1,2,3,1};
int target = 1;
在这种情况下，数组旋转之后的两个升序部分分别为[1,1,2,3]和[1]，加上我们的target的值是1，在两个升序空间中都出现了，这也就是我们说的不确定情况。
这种情况下如果通过判断条件选定查找空间就可能会出现错误。
怎样解决
我认为这种情况，最不容易出错的方法是，首先找到数组旋转的“头”所在的索引位置，然后分别在两个升序部分中分别搜索，找到的最小的索引值即为符合题目要求的索引位置。
遇到需要分别在两个部分寻找索引的情况可以使用递归二分法的形式来实现。
模板二
模板二是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
代码
//模板二
//查找元素的右邻居/得到元素的左侧边界
/**
* 注意:
* 这里的区间遍历区间换成了
* low = mid+1;high = mid
* 原因为：
* 因为现在的循环条件变成了 while(low<high)而不是 while(low<=high)
* 所以相当于循环遍历的空间为[low,high),是一个左闭右开空间
* 所以分割之后的遍历空间也是左闭右开空间,即为：
* [low,mid),[mid+1,high)
*
*/
public static int findL(int[] nums,int target){
int low = 0;
int high = nums.length;
int mid;
while(low<high){
mid = low+((high - low)>>1);
if(nums[mid] == target){
return mid;
//high = mid;
}
else if(nums[mid]>target){
high = mid;
}else {
low = mid+1;
}
System.out.println(low+" "+high);
}
if(low!=nums.length && nums[low] == target)
return low;
return -1;
}
关键属性
- 一种实现二分查找的高级方法。
- 查找条件需要访问元素的直接右邻居。
- 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
- 保证查找空间在每一步中有2个元素。
- 需要进行后续处理。当剩下一个元素时，循环/递归结束。需要评估剩下的元素是否符合条件。
区分语法
- 初始条件：left = 0，right = length；
- 终止：left==right；
- 向左查找：right = mid；
- 向右查找：left= mid+1；
例题
基础定位题型：
定位一个排序数组中某个元素的值，假设数组中可能存在重复值，如果存在，则返回最小的索引值。例如：
int arr[] = {1,1,1,1,2,3};
int target = 1;
返回值：0（0为元素1所在的最小位置的索引）
这种条件下只需要将模板代码稍作修改即可。
public static int findL(int[] nums,int target){
int low = 0;
int high = nums.length;
int mid;
while(low<high){
mid = low+((high - low)>>1);
if(nums[mid] == target){
high = mid;
}
else if(nums[mid]>target){
high = mid;
}else {
low = mid+1;
}
System.out.println(low+" "+high);
}
if(low!=nums.length && nums[low] == target)
return low;
return -1;
}
寻找旋转排序数组中的最小值
代码
class Solution {
public int findMin(int[] nums) {
int low = 0;
int high = nums.length-1;
int mid;
while ((low<high)){
mid = low+((high-low)>>1);
//当首元素的值小于尾元素时，说明该区间已经是一个单增区间
//即说明首元素是最小元素
if(nums[low] < nums[high])
return nums[low];
//这里必须是大于等于条件
if(nums[mid]>=nums[low]){
low = mid+1;
}else{
high = mid;
}
}
return nums[low];
}
}
为什么用到了模板二呢？
因为最小值所处的位置，可以看成是第二个升序空间的开头元素。
在查找时，当定位到某一个mid元素，我们要判断的就是当前元素所在的区间是哪一个。
如果在第一个区间，那么开头元素肯定不在这个区间，则查找右半部分的区间，这时的判断条件应该为：low = mid+1；
如果当前元素在第二个区间，那么说明首元素肯能就是当前元素也可能在当前元素之前，所以需要在左半部分继续查找，这时的判断条件为 ：high = mid。
这正好符合模板二的条件呀~。
模板三
模板三和模板二十分相似，模板二是用来查找左边界的，那么模板三就是用来查找右边界元素的。这里不详细讲啦！
//模板三
//得到元素的右侧边界
public static int findR(int[] nums,int target){
int low = 0;
int high = nums.length;
int mid;
while (low<high){
mid = low + ((high-low)>>1);
if(nums[mid] == target){
//return mid;
low = mid+1;
}
else if(nums[mid]>target){
high = mid;
}else{
low = mid+1;
}
}
if(low!=0 && nums[low-1] == target)
return low-1;
return -1;
}
注意：
模板三和模板二的区别主要在当nums[mid]==target的时候，模板二将向左半部分区间“缩小”连同mid位置的值作为边界继续查找；而模板三则正好相反，将向右半部分区间“缩小”并连同mid位置的值作为边界继续查找。
模板四
是二分查找的另一种独特形式。它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
//模板四
//查找元素的左右邻居元素
public static int findLR(int[] nums,int target){
int low = 0;
int high = nums.length-1;
int mid;
while(low+1<high){
mid = low+((high-low)>>1);
if(nums[mid] == target){
return mid;
}
else if(nums[mid]>target){
high = mid;
}else{
low = mid;
}
}
if(nums[low] == target)
return low;
if(nums[high] == target)
return high;
return -1;
}
关键属性
- 实现二分查找的另一种方法。
- 搜索条件需要访问元素的直接左右邻居。
- 使用元素的邻居确定他是向左还是向右。
- 保证查找空间在每个步骤中至少有3个元素。
- 需要进行后续处理。当剩下两个元素时，循环/递归结束。需要评估其余元素是否符合条件。
区分语法
- 初始条件：low = 0；high = nums.length-1;
- 终止条件：low+1 == high；
- 向左查找：high = mid；
- 向右查找：low = mid;
例题
解题思路
首先，我们需要在数组中定位到最接近x值的数的索引位置，这个值可能等于x，也可能不等于x值。
其次当我们找到这个索引位置后，可以以这个索引位置为中心向左和向右移动（k-1）个位置，作为我们要查找的数值范围的最大区间，因为我们要查找的数一定在这个区间中，这两个区间端点可以用两个指针（双指针）来定位。
定位好之后，通过比较前后两个端点与x值的差值来缩小这个端点区间，知道这个区间中的数等于k，循环结束。
这时区间中的数也就是我们要找的答案。
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> list = new ArrayList<>();
if(x<arr[0]){
for(int i =0;i<k;i++){
list.add(arr[i]);
}
return list;
}else if(x>arr[arr.length-1]){
for(int i =arr.length-k;i<arr.length;i++){
list.add(arr[i]);
}
return list;
}
int locate = find(arr,x);
int i = Math.max(locate-(k-1),0);
int j = Math.min(arr.length-1,locate+(k-1));
int num = j-i+1;
while(num!=k){
if(Math.abs(arr[i] - x)<=Math.abs(arr[j]-x)){
j--;
} else{
i++;
}
num = j-i+1;
}
for(int m = i;m<=j;m++){
list.add(arr[m]);
}
return list;
}
public int find(int[] nums,int target){
int low = 0;
int high = nums.length-1;
int mid;
while(low+1<high){
mid = low+((high-low)>>1);
if(nums[mid] == target){
return mid;
}else if(nums[mid]>target){
high = mid;
}else {
low = mid;
}
}
if(nums[low]<=target && Math.abs(nums[low]-target)<=Math.abs(nums[high]-target))
return low;
else
return high;
}
}
那么为什么这道题用到了模板三呢？
仔细看题目要求，我们发现，当数组中的两个值都与x值相差相等时，需要返回较小的那个数，这就涉及到了查找时的选择问题。举个简单的例子：
int arr[] = {1,3};
int x = 2;
int k = 1;
这也是我在测试中遇到的一个例子，首先在定位哪个值离2最近时，如果不加选择，就可能定位成3对应的索引，但其实1和2的差值也是1并且比3更小，所以应该返回的索引是0，这种情况下，模板三就派上用场啦，可以在最后判断一下1和3哪个和2的差值更小，差值相同的条件下返回更小的值对应的索引。
总结
以上就是对二分查找模板的初步总结，还有很多有意思的题型没练习和总结到。