二分查找的最坏情况是什么

Question

一个元素应该位于数组中的什么位置，使得二分搜索算法的运行时间为 O(log n)？

Answer 1

// Java 迭代二分查找的实现

class BinarySearch
{
    // Returns index of x if it is present in arr[], 
    // else return -1
    int binarySearch(int arr[], int x)
    {
        int l = 0, r = arr.length - 1;
        while (l <= r)
        {
            int m = l + (r-l)/2;

            // Check if x is present at mid
            if (arr[m] == x)
                return m;

            // If x greater, ignore left half
            if (arr[m] < x)
                l = m + 1;

            // If x is smaller, ignore right half
            else
                r = m - 1;
        }

        // if we reach here, then element was 
        // not present
        return -1;
    }

    // Driver method to test above
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = {2, 3, 4, 10, 40};
        int n = arr.length;
        int x = 10;
        int result = ob.binarySearch(arr, x);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at " + 
                                   "index " + result);
    }
}

时间复杂度： Binary Search的时间复杂度可以写成

T(n) = T(n/2) + c 上述递归可以使用递归树方法或Master方法来解决。它属于Master Method的情况II，并且递归的解决方案是Theta（Logn）。

辅助Space：在迭代实现的情况下为O(1)。在递归实现的情况下，O(Logn)递归调用堆栈space.

Answer 2

第一个或最后一个元素将在二进制搜索中给出最坏情况的复杂性，因为您必须进行最大数量的比较。示例：

1 2 3 4 5 6 7 8 9

这里搜索 1 会给你最坏的情况，结果在第 4 遍中出现。

1 2 3 4 5 6 7 8

在这种情况下，搜索 8 将给出最坏的情况，结果为 4 遍。

请注意，在第二种情况下，搜索 1（第一个元素）只需 3 遍即可完成。（比较 1 和 4，比较 1 和 2，最后比较 1）

所以，如果没有。的元素是偶数，最后一个元素给出了最坏的情况。

这是假设所有数组都是 0 索引的。发生这种情况是因为将 mid 视为 (start + end) /2 的浮点数。

二分查找的最坏情况是什么

What is the worst case for binary search

search

runtime

binary-search

time-complexity