二分搜索算法

原文：https://www.studytonight.com/data-structures/binary-search-algorithm

二分搜索应用于大尺寸的排序数组或列表。与其他排序算法相比， O(log n) 的时间复杂度使其非常快。唯一的限制是必须对元素的数组或列表进行排序，二分搜索算法才能对其进行处理。

实现二分搜索算法

以下是我们将遵循的实施步骤:

  1. 从中间元素开始:
    • 如果目标值等于数组的中间元素，则返回中间元素的索引。
    • 如果不是，则将中间元素与目标值进行比较，
      • 如果目标值大于中间索引中的数字，则选择中间索引右侧的元素，并从步骤 1 开始。
      • 如果目标值小于中间索引中的数字，则选择中间索引左侧的元素，并从步骤 1 开始。
  2. 找到匹配项时，返回匹配元素的索引。
  3. 如果没有找到匹配，则返回-1
/*
    function for carrying out binary search on given array
    - values[] => given sorted array
    - len => length of the array
    - target => value to be searched
*/
int binarySearch(int values[], int len, int target)
{
    int max = (len - 1);
    int min = 0;

    int guess;  // this will hold the index of middle elements
    int step = 0;  // to find out in how many steps we completed the search

    while(max >= min)
    {
        guess = (max + min) / 2;
        // we made the first guess, incrementing step by 1
        step++;

        if(values[guess] ==  target)
        {
            printf("Number of steps required for search: %d \n", step);
            return guess;
        }
        else if(values[guess] >  target) 
        {
            // target would be in the left half
            max = (guess - 1);
        }
        else
        {
            // target would be in the right half
            min = (guess + 1);
        }
    }

    // We reach here when element is not 
    // present in array
    return -1;
}

int main(void)
{
    int values[] = {13, 21, 54, 81, 90};
    int n = sizeof(values) / sizeof(values[0]);
    int target = 81;
    int result = binarySearch(values, n, target);
    if(result == -1)
    {  
        printf("Element is not present in the given array.");
    }
    else
    {
        printf("Element is present at index: %d", result);
    }
    return 0;
}

希望以上代码清晰，如有疑惑，请在我们 Q & A 论坛发帖提问。

现在让我们试着理解，为什么二分搜索的时间复杂度是 O(log n) 以及我们如何在不做任何计算的情况下，使用二分搜索计算从给定数组中搜索一个元素所需的步骤数。超级简单！你准备好了吗？

二分搜索的时间复杂度O(log n)

当我们说时间复杂度是log n时，我们实际上是指log<sub>2</sub> n，虽然对数的基数在渐近符号中并不重要，但是为了更好地理解这一点，我们通常考虑基数为 2。

我们先来了解一下log<sub>2</sub>(n)是什么意思。

表达式:log 2 (n) - - - - - - - - - - - -对于 n = 2:log2(21)= 1 Output = 1------------对于 n = 4 log 2 (2 2 ) = 2 Output = 2 - - - - - - - - - - - - - - -对于 n = 8 log2(23)= 3 Output = 3------------对于 n = 256 log2(28) = 8 输出= 8 - - - - - -对于 n = 2048 log2(211)= 11 输出= 11

既然我们知道了log<sub>2</sub>(n)如何与n的不同值一起工作，那么我们就更容易将其与二分搜索算法的时间复杂度联系起来，也更容易理解我们如何能够找出使用二分搜索搜索任意数量的n的任意值所需的步骤数。

计算步数

正如我们已经看到的，每出现一个不正确的guess，二分搜索就把元素列表减少一半。因此，如果我们从 32 个元素开始，在第一次不成功的猜测之后，我们将剩下 16 个元素。

所以考虑一个有 8 个元素的数组，在第一次不成功之后，二分搜索会把列表减少一半，留下 4 个元素，然后在第二次不成功的猜测之后留下 2 个元素，最后只剩下 1 个元素，要么是target要么不是，检查还需要一步。因此，总的来说，二分搜索最多需要 4 次猜测才能在一个有 8 个元素的数组中搜索到target。

如果列表的大小是 16，那么在第一次不成功的猜测之后，我们会剩下 8 个元素。之后，正如我们所知，我们需要 4 次猜测，加上 1 次猜测，将列表从 16 个减少到 8 个，这样我们就有了 5 次猜测。

所以我们可以说，随着元质数量的增加，找到target所需的猜测数量会增加1。

看到模式了吗？

概括起来，我们可以说，对于具有n元素的数组，

我们可以重复减半的次数，从n开始，直到得到值 1，再加 1。

你猜怎么着，在数学中，函数log<sub>2</sub> n的意思完全一样。我们已经看到上面的日志功能是如何工作的，你注意到了吗？

对于n = 8，log<sub>2</sub> n的输出结果是3，这意味着数组最大可以减半 3 倍，因此寻找目标值的步数(最多)为(3 + 1) = 4。

问你一个问题:在 2，097，152 元素列表中搜索一个数字，二分搜索需要的最大猜测次数是多少？

现在我们已经学习了二分搜索算法，您还可以学习其他类型的搜索算法及其应用: