有序搜索

指令

编写一个函数，接收一个整数的有序数组和一个整数。如果目标数字存在于数组中，返回其索引；若不存在，返回 -1。

输入：整数数组，整数
输出：整数（目标值的索引；不存在时返回 -1）

示例：

1search([1, 3, 6, 13, 17], 13); // -> 3
2search([1, 3, 6, 13, 17], 12); // -> -1

---

1function search(numbers, target) {
2    // 你的代码在这里
3}

---

解法一

1function search(numbers, target) {
2    for(let i = 0; i < numbers.length; i++) {
3        if(numbers[i] === target) {
4            return i;
5        }
6    }
7    
8    return -1;
9}

该解法非常简单。我们遍历整个数组，寻找目标值。

时间复杂度

由于需要遍历整个数组，时间复杂度为：

O(n)

空间复杂度

因为我们只使用固定数量的变量，空间复杂度为：

O(1)

---

二分查找

我们可以提出一个更优的解决方案。由于数组是有序的，我们可以跳过部分区域，快速定位目标索引。

查找单词的类比

想象一下在字典中查找一个单词。如果逐个翻阅每个单词，直到找到目标，这显然效率极低。更好的方法是先打开字典中间的位置。如果目标单词在中间页的字母顺序之前，那么它一定在书的前半部分。

接着可以翻到约四分之一的位置，再次判断目标在前半还是后半。通过不断排除一半的范围，我们可以迅速缩小查找区间。

重复这个过程，即使字典非常大，也能远快于逐个查找。

扩展性分析

事实上，如果字典规模翻倍（增加更多单词），我们只需多执行一次判断步骤。尽管字典变厚了，但额外的工作量几乎可以忽略。

现在我们将这种思路转化为代码。

解法二

1function binarySearch(numbers, target) {
2    let startIndex = 0;
3    let endIndex = numbers.length - 1;
4
5    if(target < numbers[startIndex] || target > numbers[endIndex]) {
6        return -1;
7    }
8    
9    while(true) {
10        if(numbers[startIndex] === target) {
11            return startIndex;
12        }
13        
14        if(numbers[endIndex] === target) {
15            return endIndex;
16        }
17        
18        if(endIndex - startIndex <= 1) {
19            // 表示目标值不存在
20            return -1;
21        }
22        
23        const middleIndex = Math.floor((startIndex + endIndex) / 2);
24        
25        if(target > numbers[middleIndex]) {
26            startIndex = middleIndex + 1;
27        } else if(target < numbers[middleIndex]) {
28            endIndex = middleIndex - 1;
29        } else {
30            return middleIndex;
31        }
32    }
33}

工作原理

我们首先确认目标值是否在数组范围内，若不在则直接返回 -1。

在循环中，我们先检查目标值是否等于数组起始或结束位置的元素。然后比较目标值与中间位置元素的大小关系。

• 如果目标值小于中间值，说明它位于数组的前半部分，我们只需关注前半段。
• 如果目标值大于中间值，说明它不可能出现在前半部分，应转向后半部分查找。

每次迭代都将待查范围缩小一半，直到最终定位到目标值或确定其不存在。一旦找到目标，立即返回其索引。

如果最终 startIndex 与 endIndex 相邻（即 endIndex - startIndex <= 1），说明目标值夹在两个元素之间，因此返回 -1。

时间复杂度

每轮循环都使搜索范围减半，因此时间复杂度为：
O(log₂(n))，可简化为：

O(log(n))

空间复杂度

空间复杂度仍为：

O(1)

---

总结

处理有序数据时，我们可以进行多种优化。因为已知元素与其前后元素之间的相对顺序，因此可以跳跃式地定位目标值。

当数据未排序时，有时值得先将其排序。如果原本的算法时间复杂度为 O(n²)，不妨考虑先排序。

排序本身的时间复杂度为 O(n log n)，优于 O(n²)。排序完成后，后续操作通常为线性或对数级别，其开销相比排序本身可忽略不计。