Бинарный поиск в массиве
- //Программная реализация бинарного поиска может иметь следующий вид
- Procedure Search;
- Var
- i, j, m: Integer;
- f: Boolean;
- Begin
- i:=1; j:=N; //На первом шаге рассматривается весь массив
- f:=False; //Признак того, что X не найден
- While (i<=j) And Not f Do
- Begin
- m:=(i+j) Div 2; //Или m:=i+(j-i) Div 2;
- If A[m]=X Then f:=True //Элемент найден, поиск прекращается
- Else If A[m]<X Then i:=m+1 //Исключаем из рассмотрения левую часть A
- Else j:=m-1;
- End;
- End;
- //Рекурсивная реализация поиска. Значением переменной t является индекс искомого элемента или ноль, если элемент не найден.
- Procedure Search(i,j: Integer; Var t: Integer);
- //Массив A и переменная X - глобальные величины
- Var m: Integer;
- Begin
- If i>j Then t:=0 Else
- Begin
- m:=(i+j) Div 2;
- If A[m]<X Then Search(m+1,j,t) Else
- If A[m]>X Then Search(i,m-1,t) Else t:=m;
- End;
- End;
• Подробнее о бинарном (двоичном) поиске в Wikipedia.
