【算法】二分查找

目录

一、概念

二、思路

三、边界问题

---

一、概念

在一本书中查找某一页，我们总是倾向于先翻到整本书的中间，然后根据当前页数判断我们想要找的页在当前页的左半本中还是右半本中，接着继续翻到剩下半本书的中间......

这就是二分查找思想在现实中的应用，但为什么这种方法能够比较快的查找到我们想要的页数？这是因为书中的页数是有序的，通过当前页数与目标页数的比较，我们能够确保目标页在当前页的左侧还是右侧

---

二、思路

二分查找的时间复杂度为O(logN)，但是只适用于在有二分性质的序列中进行查找

二分性质：即我们可以自定义一个性质，让区间的左半部分都不满足，右半部分都满足 

最朴素的场景：有序的数组

• 以下面的有序数组为例，首先用l和r维护我们需要二分的区间

• 取区间的中点，判断中点值与我们的目标的大小关系

注意，如果区间元素的个数是奇数，那么只有一个中点；但如果元素个数是偶数，那么就会存在两个中点，例如上面的5和7都是中点

此处我们只讨论比较特殊的情况，即有偶数个元素的情况

对于该情况，我们可以选择每次取区间的左中点或右中点

取左中点：

int mid = (l + r) / 2;
int mid = l + (r - l) / 2; //防溢出

如果采用上面(l + r) / 2的方式来取左中点，如果l和r的值过大则有数值溢出的风险，因此建议使用第二个的方式

取右中点：

int mid = (l + r + 1) / 2;
int mid = l + (r - l + 1) / 2; //防溢出

由于除法向下取整，因此如果元素个数为奇数，不论是以取左中点的方式还是取右中点的方式，我们都能够取到中点，例如：

下面以偶数个元素为例

• 以取左中点为例，我们取左中点值5

• 5比8小，且我们的数组是升序的，则要查找的目标在右半部分

• 重复上述步骤

要理解二分查找的思路并不难，有难度的地方在于其边界问题的处理

---

三、边界问题

以取左中点为例，我们先来看正确的代码

int Binary_Search(int* a, int sz, int x) //假设数组升序
{int l = 0, r = sz - 1; //区间左右边界while(l < r){int mid = l + (r - l) / 2; //取左中点if(a[mid] > x) //中点值比x大：目标在左半部分r = mid;else if(a[mid] < x) //中点值比x小：目标在右半部分l = mid + 1; else //相等return mid; //返回下标}//走出循环，说明l==r，判断此时位置是否与x相等if(a[l] == x)return l;return -1;
}

可以看到，当中点值比x大时，目标在左半部分，r移动到原来mid的位置；但当中点值比x小时，目标在右半部分，而l却移动到了mid+1的位置。为什么不是和r一样移动到mid？

我们看一个最简单的例子

只有两个元素，中点mid与l位置重合，且目标为2大于中点值1，此时l需要移动到mid+1的位置

可以正常找到我们的目标

但如果上一步中，l移动到mid的位置会怎么样呢？l和mid的位置本来就是重合的，移动过后位置没有改变，导致死循环

这说明，不论是取左中点还是右中点，一旦边界问题没有处理好，那么就会导致死循环

取右中点的代码：

int Binary_Search(int* a, int sz, int x) //假设数组升序
{int l = 0, r = sz - 1; //区间左右边界while(l < r){int mid = l + (r - l + 1) / 2; //取右中点if(a[mid] > x) //中点值比x大：目标在左半部分r = mid - 1;else if(a[mid] < x) //中点值比x小：目标在右半部分l = mid; else //相等return mid; //返回下标}//走出循环，说明l==r，判断此时位置是否与x相等if(a[l] == x)return l;return -1;
}

修改对应取中点的方式，并修改r和l的移动方式即可，原理和上面是相同的

如果不想考虑边界情况，则还有一种方式：

int Binary_Search(int* a, int sz, int x) //假设数组升序
{int l = 0, r = sz - 1; //区间左右边界while(l <= r){int mid = l + (r - l) / 2; //取左中点//int mid = l + (r - l + 1) / 2; //取右中点if(a[mid] > x) //中点值比x大：目标在左半部分r = mid - 1;else if(a[mid] < x) //中点值比x小：目标在右半部分l = mid + 1; else //相等return mid; //返回下标}return -1;
}

在这种方式下，r和l移动后都不会与原来的mid位置重合

完.