排序与查找
二分查找
二分查找在有序列表中找值的办法，是不断把可能的范围对半砍掉。看中间那个元素：若它正是目标，就找到了；若目标更小，就丢掉整个上半部分；若更大，就丢掉下半部分。每看一次，剩下的就少一半。这正是你在词典里查单词的方式——你不会从第 1 页读起，而是翻到中间，再决定往哪边走。
其机制是一个由两个下标 low 和 high 框定、不断收缩的窗口，中间取 mid = (low + high) / 2。每次比较让 low 上移或 high 下移，窗口便持续合拢；当找到目标、或窗口为空（low > high）时搜索结束。唯一不可商量的前提是：数据必须按你比较的键有序——在无序数据上，“丢掉一半”的推理就站不住脚了。
反复对半正是它飞快的原因：从 n 个元素出发，约 log2(n) 步就能收敛到唯一候选——时间 O(log n)，额外空间 O(1)。一百万个元素也只需约二十次比较。代价是你必须保持数据有序（且放在支持快速随机访问的结构里，比如数组）；若只是在无序数据里做一次性查找，朴素的线性查找也许更省事。
int binarySearch(const std::vector<int>& a, int target) {
int low = 0, high = (int)a.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) low = mid + 1; // go right
else high = mid - 1; // go left
}
return -1; // not found
}每一步都把搜索范围对半减少，所以 n 个元素的有序数组只需约 log2(n) 次比较。
用 mid = low + (high - low) / 2 而不是 (low + high) / 2；在超大数组上，后者会因 low + high 超出整数上限而溢出。这是许多教科书实现里有名的 bug。
又称
另见