Оптимизированный двоичный поиск

Я видел много примеров бинарного поиска, много методов его оптимизации, поэтому вчера мой лектор написал код (в этом коде предположим, что первый индекс начинается с 1, а последний - N, так что N - длина массива, рассмотрим это в псевдокоде. код выглядит так:

L:=1;
R:=N;
while( L<R)
{
m:=div(R+L,2);
 if A[m]> x
{
 L:=m+1;

}
else
{
 R:=m;

}
}

Здесь мы предполагаем, что массив - это A, поэтому лектор сказал, что мы не тратим время на сравнение, если элемент находится в средней части массива каждый раз, также преимущество состоит в том, что если элемент не в массиве, индекс говорит о том, где он будет расположен, так что это оптимально, он прав? Я имею в виду, что я видел много видов бинарного поиска, например, от Джона Бентли (жемчужины программирования) и так далее, и действительно ли этот код оптимален? в моем случае он написан паскалем, но язык не зависит.


optimization binary-search
person Aleksi Beriashvili    schedule 10.10.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Это действительно зависит от того, найдете ли вы элемент. Если вы этого не сделаете, это сэкономит некоторые сравнения. Если вы смогли найти элемент за первые несколько прыжков, значит, вы сохранили работу всех последующих сравнений и арифметических операций. Если все значения в массиве различны, очевидно, что вы вряд ли попадете в нужный индекс на раннем этапе, но если у вас есть широкие участки массива, содержащие одинаковые значения, это меняет математику.

Этот подход также означает, что вы не можете сузить диапазон совсем так сильно, как в противном случае - это:

R:=m;

обычно было бы

R:=m-1;

... хотя это редко может иметь существенное значение.

Важным моментом является то, что это не меняет общую сложность алгоритма - она ​​по-прежнему будет O (log N).

также преимущество заключается в том, что если элемент отсутствует в массиве, индекс говорит о том, где он будет расположен

Это верно независимо от того, проверяете ли вы равенство или нет. Каждая реализация двоичного поиска, которую я видел, давала такую ​​информацию.

person Jon Skeet    schedule 10.10.2012
comment
Значит, это оптимально, и я мог бы использовать его в реальном программировании, верно? - person Aleksi Beriashvili; 10.10.2012
comment
@AleksiBeriashvili: Тут более тонкие нюансы. В некоторых случаях он будет работать лучше, чем альтернативы, в некоторых случаях он будет работать хуже. Однако большинство платформ имеют встроенный двоичный поиск - вам вообще не нужно разрабатывать его самостоятельно. - person Jon Skeet; 10.10.2012