北京
打开一本按字母排序的词典，找一个以 L 开头的单词。你不会从第一页翻起，而是一把翻到中间。如果中间那页是 M，L 在 M 前面，右半边整本可以直接扔掉；如果中间是 K，L 在 K 后面，左半边同样作废。重复这个动作，直到翻到那一页。
这就是二分查找的全部直觉。它靠的是分治思路：每一步都把剩余的搜索空间砍掉一半。和从头到尾逐个比对的线性查找放在一起，差距在数据量变大后会变得非常明显。
前提只有一个：数据必须有序
二分查找要能跑起来，搜索空间必须是排好序的，或者至少是单调的——持续递增或持续递减。如果数据是乱序的，你没有任何依据判断目标落在哪一半，也就没法丢掉任何一半。这条前提不满足，后面所有步骤都不成立。
两个指针，四步循环
整个算法用两个索引指针圈定搜索范围：low（左边界，范围起点）和 high（右边界，范围终点）。之后就是一套固定的逻辑：
初始化：low = 0，high = N - 1，N 是数据集里的元素个数。
算出当前范围的中点索引 mid。
拿 mid 位置的元素和目标值比较。
根据比较结果收缩边界，然后重复第 2、3 步，直到 low 越过 high。
第 3 步的比较有三种结果，对应三种动作：
相等：mid 位置的元素就是目标，直接返回 mid。
mid 元素大于目标：目标只可能在左半边，把上边界收进来，high = mid - 1。
mid 元素小于目标：目标只可能在右半边，把下边界抬上去，low = mid + 1。
循环的继续条件是 low 不超过 high。一旦两个指针交叉，说明范围已经空了，目标不在这个集合里。
拿 [1, 3, 5, 7, 9] 找 7 走一遍
第一轮：low = 0，high = 4。中点 mid = 0 + Math.floor((4 - 0) / 2) = 2，索引 2 上的元素是 5。5 小于目标 7，目标在右半边，下边界更新为 low = mid + 1 = 3。
第二轮：low = 3，high = 4。中点 mid = 3 + Math.floor((4 - 3) / 2) = 3，索引 3 上的元素是 7。和目标相等，命中，函数在这里停下并返回索引 3。
五元素的数组，两轮就结束。数组越长，这种折半的优势越明显——每比较一次，待查范围就少一半。
上边界开闭，两种写法都行
上面的实现用的是闭区间上界，也就是 high 这个索引本身包含在搜索循环里。也有开发者习惯用开区间上界，把 high 设成 arr.length。选开区间的话，循环条件要改成 while (low < high)，右侧边界的收缩方式也要相应改成 high = mid。
两种写法都能正常工作。开区间上界在找缺失元素的插入位置这类场景里更好用一些。
代码骨架大致是这样：循环里先算 mid，命中就返回；mid 元素大于目标就把 high 收到 mid - 1，否则把 low 抬到 mid + 1；循环走完还没命中，返回 -1。
逻辑改动很小，但数组一大，性能上的差别就出来了。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
