二分查找

简介

你遇到了一群既研究数学又写歌的人。他们为喜爱的每个数字都写了一首歌，例如 0、73、6174，数量十分可观。

你想听自己最喜欢的数字对应的歌曲，但逐首寻找可能很慢。幸好，歌单已按标题排序，而标题就是相应数字。

你意识到可以使用二分查找，根据标题快速找到歌曲。

任务说明

实现二分查找算法。

二分查找反复把列表分成两半，只保留可能包含目标的一半，从而快速缩小范围，直到找到目标或排除全部位置。

注意 二分查找要求列表已经有序。

算法过程如下：

• 找到有序列表的中间元素，与目标比较。
• 若相等，查找完成。
• 若中间元素大于目标，排除它及其后面的所有元素。
• 若中间元素小于目标，排除它及其前面的所有元素。
• 若所有元素都已排除，目标不在列表中。
• 否则在剩余部分重复上述过程。

例如：

在有序列表 [4, 8, 12, 16, 23, 28, 32] 中寻找 23。

• 先比较 23 和中间值 16。
• 23 大于 16，排除左半部分，剩下 [23, 28, 32]。
• 再比较 23 和新的中间值 28。
• 23 小于 28，排除右侧，剩下 [23]。
• 找到目标。