Бинарная отбивная: если список [средний] == ключевой регистр

Question

Я пересматриваю алгоритмы для своих экзаменов, и я пытался решить это упражнение, но я не мог найти решение.

Это псевдокод.

1. int search (int [] a, int x) {
2. // Pre: ∃i:Nat (0≤i<a.length ∧ a[i]=x) ∧ a is in ascending order
3. // Post: 0≤ r≤ a.length ∧
4. // ∀i:int.(0 ≤ i < r → a[i] < x) ∧ a[r]=x
5. int left, middle; int right = a.length;
6. if (a[0]>=x) return 0; else left=0; //a[left]<x (a)
7. while ((right-left>1){ (b)
8. // invariant: (I1) 0≤ left < right ≤ a.length ∧
9. // (I2) ∀i:int(0 ≤ i ≤ left → a[i] < x) ∧
10. // (I3) ∀i:int(right ≤ i < a.length → a[i] > x)
11. // (note: a[i]>x not a[i]≥x)
12. // Variant: right-left-1
13. middle = (left+right) / 2; // left < middle < right (*)
14. if ( a[middle]== x) return middle;
15. else {if a[middle)<x) left = middle ;
16. else right=middle;} (c)
17. }
18. } // left+1=right } (d)

Итак, код в том виде, в каком он есть сейчас, не удовлетворяет условию post, потому что для определенных входных данных (например, x = 1 и a = {0,1,1,1,1}) значение, возвращаемое строкой 14, не ' t удовлетворяет постусловию в строке 4. Упражнение просит: «Заменить« return middle; »в строке 14. на цикл while и return код, чтобы он удовлетворял постусловию. Включить вариант и инвариант достаточно сильный, чтобы подразумевать постусловие по возвращении. Подсказка: не забудьте указать, что не меняется. "

Мне не удалось найти решение. Кто-нибудь может мне помочь?

Спасибо заранее, VJ

EDIT: Хорошо, спасибо вам обоим за помощь.

while(middle > 0 && a[middle] == x){
middle--;

} возврат среднего;

Я выбрал вариант для среднего. И инвариант должен быть:

0x

Считаете ли вы, что это правильно?

Answer 1

Ajuc опубликовал решение с использованием цикла, но, как он сказал, это может быть медленным.

Более быстрый подход - снова использовать бинарный поиск в левом массиве.Если он не найден, вернуть i, иначе вернуть результат этого двоичного поиска.Сложность останется прежней (O (logn)).

Так как это выглядит как домашнее задание, я позволю вам выяснить все остальное самостоятельно:).

Answer 2

Когда [среднее] = x, мы уверены, что мы должны вернуть индекс среднего или что-то перед ним, если есть те же значения перед серединой.

Итак

if (a[middle]==x) {
    while (--middle>0 && a[middle]==x) {};
    return middle+1;
}

Но этоможет быть медленным, например, когда целое a содержит одинаковые значения, оно имеет линейную сложность по времени.