【浅谈算法】二分查找（保姆级）

一、原理

首先，二分查找是一种简单的算法，大大减少了时间复杂度，其输入是一个有序的元素列表。

工作原理

我随便想一个1～100的数字。

你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。

假设你从1开始依次往上猜，猜测过程会是这样。

这是一种比较糟糕的查找方法，如果你想要的数字是99，那么就得查找99次，挨个查找，效率大大减小了。

接下来，在有序数组中，介绍一个高效的方法。

1、从 50 开始。

小了，但排除了一半的数字！至此，你知道1～50都小了。

2、接下来，你猜75。

大了，那余下的数字又排除了一半！那么范围就缩小在50~74之间

3、接下来，你猜63（50和75中间的数字）。

以此类推，猜测中间的数字，减少一半的可能性，这就是二分查找

假设字典包含240 000个单词，如果要查找的单词位于字典末尾，使用简单查找将需要240 000步。使用二分查找时，每次排除一半单词，只需要18步，少了很多。

时间复杂度：log₂N

二、在数组中的实现

假设，我们现在在一个数组中，需要查找一个数，k=7，对应的数组下标为6。

1、首先找中间的数字

mid=（L+R）/ 2 = （0+9）/ 2 = 4

会发现，得到的数字是5（数组下标是4），比我们想得到的数字（k=7）小

2、mid向右移动一个，L=mid，再去找中间的数字

mid=（L+R）/ 2 =（5+9）/ 2 = 7

会发现，得到的数字是8（数组下标是7），比我们想得到的数字（k=7）大

3、此时，mid向做移动一个数字，并且R=mid，再去找中间的数字

mid=（L+R）/ 2 = （5+6）/ 2 = 5

会发现，得到的数字是6（数组下标是5），比我们想得到的数字（k=7）小

4、继续找中间的数字，L=R，刚好找到

mid=（L+R）/ 2 = （6+6）/ 2 = 6

三、代码的实现

# define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int  main() {
  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
  int k;
  scanf("%d", &k);     //输入你所需要查找的数字
  int sz = sizeof(arr) / sizeof(arr[0]);
  int left = 0;
  int right = sz - 1;
  int mid = 0;
  int find = 0;    //假设如果没有找到
  while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] < k) {
      left = mid + 1;
    }
    else if (arr[mid] > k) {
      right = mid - 1;
    }
    else {
      printf("找到了，对应数组下标为%d\n", mid);
      find = 1;
      break;
    }
  }
  if (find == 0) {
    printf("很遗憾，没有i找到。\n");
  }
  return 0;
}

如果left和right⽐较⼤的时候可能存在问题，可以使⽤下⾯的⽅式：mid = left+(right-left)/2;

四、题目练习

牛可乐和魔法封印

[USACO 2009 Dec S]Music Notes