Какой наихудший случай для бинарного поиска

Question

Где должен быть элемент в массиве, чтобы время выполнения алгоритма двоичного поиска было O (log n)?

Answer 1

Первый или последний элемент даст сложность наихудшего случая в бинарном поиске, так как вам придется делать максимальное количество сравнений.Пример:

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.Это происходит из-за того, что середина считается плавающей точкой (начало + конец) /2.

Answer 2

// 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);
    }
}

Сложность времени: временная сложность бинарного поиска может быть записана как

T (n) = T (n / 2)+ c Вышеприведенное повторение может быть решено либо с использованием метода повторения, либо с помощью метода Master.Это относится к случаю II мастер-метода, и решением повторения является тэта (логн).

вспомогательное пространство: O (1) в случае итеративной реализации.В случае рекурсивной реализации пространство стека рекурсивных вызовов O (Logn).