Двоичный поиск в упорядоченном массиве
Сортировка методом вставок
Сортировка методом вставок должна быть хорошо знакома людям, играющим в карты. Представьте себе, что вам раздали карты для игры. Карты следует расставить по старшинству: слева – старшие карты, а справа – младшие. Другими словами, задача заключается в том, чтобы отсортировать полученные карты в порядке убывания. Наши действия таковы:
- первую карту отодвигаем влево.
- берем вторую карту и ставим ее либо перед первой, либо после нее в зависимости от старшинства.
- берем третью карту и также в зависимости от старшинства ставим ее либо перед первыми двумя, либо между ними, либо после них.
- действия продолжаем, пока не расставим все карты.
Отсюда и название метода – «Сортировка вставками». После очередной вставки отсортированная часть массива увеличивается на 1. Таким образом, программа имеет вид:
//Вставляем элементы, начиная со второго
for (int i=1; i<size; i++) {
<Вставить элемент с номером i
относительно элементов 0,…,i-1>
}
Для того, чтобы вставить элемент нужно отодвинуть последующие один за другим и на освободившуюся позицию поставить вставляемый:
//Вставляем элементы, начиная со второго
for (int i=1; i<size; i++) {
//Индекс вставляемого элемента
int j=i;
//Ищем позицию, куда вставить элемент
while (numbers[j]<numbers[j-1] && j!=0) {
//Меняем их местами, если
//они стоят не в том порядке
int temp = numbers[j];
numbers[j] = numbers[j-1];
numbers[j-1] = temp;
j--;
}
}
Рассмотрим теперь, как реализовать быстрый поиск, используя упорядоченность массива; для определенности будем считать, что массив отсортирован по возрастанию. Главное свойство упорядоченного массива, позволяющее осуществить эффективный поиск, заключается в том, что, если искомый элемент меньше некоторого элемента массива, то можно отбросить расположенную справа от этого элемента часть массива и продолжать поиск только по левой части. Отсюда получается следующий алгоритм. Выбрать элемент, расположенный в середине массива, и сравнить искомый элемент с ним. Если элемент окажется меньше, то выбрать середину левой части и осуществлять деление до тех пор, пока не будет равенства или массив будет состоять из одного элемента. Если он не равен, то такого элемента нет в массиве.
printf("Введите искомый элемент: ");
int x;
scanf("%d",&x);
int left = 0;
int right = size-1;
bool found = false;
while (left<=right) {
int center = left + (right-left)/2;
if (x == numbers[center]) {
found = true;
break;
} else if (x < numbers[center]) {
right = center - 1;
} else {
left = center + 1;
}
}
if (found) {
printf("Элемент %d найден\n",x);
} else {
printf("Элемент %d не найден\n",x);
}