Бинарный поиск

При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.

Алгоритм может быть определен в рекурсивной и нерекурсивной формах.

Бинарный поиск также называют поиском методом деления отрезка пополам.

Количество шагов поиска определится как

log2n↑, где n-количество элементов, - округление в большую сторону до ближайшего целого числа.
Бинарный поиск

Реализация бинарного поиска
#include <stdio.h>
#include <stdlib.h>
int main() {
  int k[20];
  int r[20];
  int key, i;
  system("chcp 1251");
  system("cls");
  k[0] = 8;
  k[1] = 14;
  k[2] = 26;
  k[3] = 28;
  ...
  k[19] = 108;
  for(i=0;i<20;i++) {
    r[i] = i+1;
    printf("%d. k[%d]= %d: r[%d]=%d\n",i,i,k[i],i,r[i]);
  }
  printf("Введите key: ");
  scanf("%d",&key);
  int low = 0;
  int high = 19;
  int search = -1;
  while (low<=high) {
    int mid=(low+high)/2;
    if (key==k[mid]) {
      search=mid;
      break;
    }
    if (key<k[mid])
      high=mid-1;
    else
      low=mid+1;
  }
  if(search==-1)
    printf("Элемент не найден!\n");
  else
    printf("%d. key= %d. r[%d]=%d",search,k[search],search,r[search])
  getchar(); getchar();
  return 0;
}

Результат выполнения
Результат бинарного поиска

Назад

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *