经典的二分查找法
二分查找法是一种基础的算法，应用于在有序元素序列中查找目标值。二分查找法思路清晰，可以描述为以下几个步骤：
- 对于一个有序元素组成的序列arr[l...r]，假设为从小到大排序，计算中间值mid=(l+r)/2；
- 比较目标值target与arr[mid]大小：
- target = arr[mid]，返回mid，程序结束；
- target < arr[mid]，更新r=mid-1，重复步骤1；
- target > arr[mid]，更新l=mid+1，重复步骤1。
二分查找法
二分查找法的代码及其简单：
int binarySearch(int arr[], int n, int target){
assert(n >= 0);
int l = 0, r = n - 1;
while (l < r){
int mid = l + (r - l) / 2;
if (arr[mid] < target){
l = mid + 1;
}
else if (arr[mid]>target){
r = mid - 1;
}
else{
return mid;
}
}
return -1;
}其中，对mid的计算改为了mid = l + (r - l) / 2,主要是避免溢出。
问题
对于下面这样一个有序序列，用上面的代码分别查找12、50和95：
测试代码如下：
int main()
{
int arr[10] = { 0,12,38,49,50,50,68,79,95,100};
printf("Position:");
for (int i = 0; i < 10; i++){
printf("%4d", i);
}
printf("\n ");
for (int i = 0; i < 10; i++){
printf(" | ");
}
printf("\nValue :");
for (int i = 0; i < 10; i++){
printf("%4d", arr[i]);
}
printf("\n\n");
printf("BinarySearch\n");
printf("binarySearch(12), Position is %d\n", binarySearch(arr, 10, 12));
printf("binarySearch(50), Position is %d\n", binarySearch(arr, 10, 50));
printf("binarySearch(95), Position is %d\n", binarySearch(arr, 10, 95));
system("pause");
return 0;
}运行结果如下图：
12和95都可以准确找到位置，因为序列中他们都只出现过一次。50的位置其实也是准确的，只不过序列中有两个50，上述算法找出来的是第1个位置的50。这是因为第一次计算出来的mid位置4就正好是50，所以直接返回了4。所以，可以理解如果是下面这样一个有序序列，使用上述代码查找50的位置，也会返回4.
有时候这样可能并不是我们想要的结果。我们可能想查找序列中第一次出现目标值，或者最后一次出现目标值，甚至是查找一个有序序列中第一个不小于目标值的元素出现的位置，或者查找第一个不大于目标值的元素出现的位置。
Ceil和Floor
为了解决上述两个问题，同样可以使用二分查找的思想设计ceil和floor函数。ceil意为天花板，即向上查找；floor意为地板，即向下查找。代码如下：
int ceil(int arr[], int n, int target){
int l = 0, r = n;
while (l < r){
int mid = l + (r - l) / 2;
if (arr[mid] <= target){
l = mid + 1;
}
else{
r = mid;
}
}
assert(l == r);
if (l - 1 >= 0 && arr[l - 1] == target){
return l - 1;
}
return l;
}
int floor(int arr[], int n, int target){
assert(n >= 0);
int l = -1, r = n - 1;
while (l < r){
int mid = l + (r - l + 1) / 2;
if (arr[mid] >= target){
r = mid - 1;
}
else{
l = mid;
}
}
assert(l == r);
if (l + 1 < n && arr[l + 1] == target){
return l + 1;
}
return l;
}接下来对上述两个函数做个测试：
int main()
{
int arr[10] = {0,12,50,50,50,50,50,50,95,100};
printf("Position:");
for (int i = 0; i < 10; i++){
printf("%4d", i);
}
printf("\n ");
for (int i = 0; i < 10; i++){
printf(" | ");
}
printf("\nValue :");
for (int i = 0; i < 10; i++){
printf("%4d", arr[i]);
}
printf("\n\n");
printf("\nCeil\n");
printf("ceil(12), Position is %d\n", ceil(arr, 12, 12));
printf("ceil(50), Position is %d\n", ceil(arr, 12, 50));
printf("ceil(80), Position is %d\n", ceil(arr, 12, 80));
printf("\nFloor\n");
printf("floor(12), Position is %d\n", floor(arr, 12, 12));
printf("floor(50), Position is %d\n", floor(arr, 12, 50));
printf("floor(80), Position is %d\n", floor(arr, 12, 80));
printf("\n");
system("pause");
return 0;
}该测试中，我们使用ceil和floor函数分别对给定的有序序列中的12、50和80进行查找。其中，
- 元素12在序列中存在，且仅有一个；
- 元素50在序列的第2~第7个位置连续出现6次；
- 元素80在序列中并不存在。
测试结果如下：
对于目标值50，ceil函数查找的结果为7，floor函数的查找结果为2。对于序列中不存在的元素80，ceil函数查找的结果为8，即95；而floor函数的结果为7。测试结果符合预期。
二分查找相关题目
LeetCode上关于二分查找的题目不少，比如：
- 69.x的平方根
- 153.寻找旋转排序数组中的最小值
- 278. 第一个错误的版本
- 540. 有序数组中的单一元素
- ……
比如第540题：
这道题直接用位运算中的异或运算，将特别痛快：
int singleNonDuplicate(vector<int>& nums) {
int ret = 0;
for (int i = 0; i<nums.size(); i++){
ret ^= nums[i];
}
return ret;
}但是题目要求时间复杂度为O(logn)，上述代码的时间复杂度为O(n)，不符合题目要求。时间复杂度为O(logn)，多半就是二分了。一番分析后，代码如下：
int singleNonDuplicate(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while (l<r){
int mid = l + (r - l) / 2;
if (mid % 2 == 0){
if (nums[mid] == nums[mid + 1]){
l = mid + 2;
}
else if (nums[mid] == nums[mid - 1]){
r = mid - 2;
}
else{
return nums[mid];
}
}
else{
if (nums[mid] == nums[mid + 1]){
r = mid - 1;
}
else if (nums[mid] == nums[mid - 1]){
l = mid + 1;
}
else{
return nums[mid];
}
}
}
return nums[l];
}二分查找法O(logn)的时间复杂度让它成为十分高效的算法。不过别忘了使用二分查找法的前提，即元素有序+数组。