инвариант бинарного поиска для нахождения первого вхождения элемента

У меня проблема с определением инварианта нахождения первого элемента бинарного поиска. (У меня есть отсортированный массив a, и я хочу найти первый элемент, равный некоторому числу q, и если он не существует, вернуть -1)

Во-первых, я установил этот инвариант на время.

Мой инвариант

«Всегда a[l]‹= q, а также a[r] > q» ==> «Всегда l ‹= ind, а также > ind».

В соответствии с моим инвариантом я написал этот код:

int l=0,r=n;
while(l<r){
    int mid=(r+l)/2;
    if(a[mid]==q){
        r=mid+1;
    }
    else{
        if(a[mid]>q){
            r=mid;
        }else if(a[mid]<q) l=mid+1;
    }
}
return l;

Но есть проблема, что if(a[mid]==q) тогда я должен выбрать r, который не нарушает мой инвариант.

Если я выберу mid-1, я нарушу его, потому что a[r] будет ‹= q.

И я должен перебирать свои индексы, пока не найду индекс I с a[i]>q, а затем установить r для этого индекса. (r=i)==>Но если я сделаю это, это не O(log n)

И я видел некоторый код, реализующий lower_bound, который if(a[mid]==q) устанавливает r в mid, но я думаю, что они нарушают их инвариант, но их код правильный и возвращает правильное значение.

Как этот код:

1- int l = 0;
2- int r = n; // Not n - 1
3- while (l < r) {
4-     int mid = (l + r) / 2;
5-     if (q <= a[mid]) {
6-         r = mid;
7-     } else {
8-         l = mid + 1;
9-     }
10- }
11- return l;

Во-первых, инвариант похож на мой инвариант (i находится в диапазоне [l,r)), но в строке 5 рассмотрим if(q==a[mid]), тогда, очевидно, он нарушает, потому что его ([l,r], потому что r равно, и это может быть первое появление).

Я прав или у меня нет правильного понимания концепции инварианта?


c++ algorithm binary-search invariants
person Aira Banazadeh    schedule 24.05.2019    source источник
comment
Я думаю, что инвариант должен быть l < x and r >= x, а затем, наконец, вернуть r   -  person Andrew Scott    schedule 24.05.2019
comment
@AndrewScoot Почему я не могу использовать этот инвариант?   -  person Aira Banazadeh    schedule 24.05.2019

Ответы (1)


arrow_upward
0
arrow_downward

Предположим, у нас есть последовательность

..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                 ^ (*)

где <q (>q) обозначает любой элемент < q (> q). Мы хотим найти точку (*).

У нас есть два указателя, left < right. Как мы можем использовать их, чтобы различить эту точку? Ответ прост: left должен указывать на последний <q элемент, right должен указывать на первый q элемент:

..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                 ^ right
             ^ left

Инвариант: *left < q и *right >= q.

Предложенный вами инвариант *left <= q и *right > q соответствует последнему элементу в этой последовательности:

..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                                  ^ right
                               ^ left

Некоторые ссылки, которые могут быть полезны:

person Evg    schedule 24.05.2019
comment
Так что в этой задаче я могу использовать только этот инвариант ==›left‹q и right›=q Правильно ли я? - person Aira Banazadeh; 24.05.2019
comment
@AiraBanazadeh, если вы хотите найти первого q, да. - person Evg; 24.05.2019
comment
Спасибо. Как я могу найти инвариант для таких вопросов? (Я имею в виду, могу ли я решить и найти инварианты всех вопросов бинарного поиска с вашей логикой в ​​вашем ответе?) - person Aira Banazadeh; 24.05.2019
comment
@AiraBanazadeh, я не могу сказать по всем вопросам бинарного поиска, но идея всегда одна и та же. Если вам нужно более подробное объяснение, взгляните на некоторые ссылки, которые я добавил к ответу. - person Evg; 24.05.2019
comment
Можете ли вы предоставить мне ссылку на PDF-файл Programming Pearls? - person Aira Banazadeh; 24.05.2019