14.2 Двоичный поиск

Двоичный поиск можно организовать на отсортированных массивах данных.

Двоичный поиск организован следующим образом: устанавливается границы поиска g1 и g2, первоначально g1=0, а g2= SIZEVECTOR-1. Далее вычисляем индекс среднего элемента (addr), используя границы g1 и g2. Затем сравниваем искомое значение с вычисленным элементом, если совпало, то нашли, если нет, то проверяем в какой части относительно элемента addr нужно искать (поскольку данные отсортированы, то на основании сравнения можно сделать вывод, в какую сторону двигаться).

#define SIZEVECTOR 10
int vector[SIZEVECTOR]= { 1, 5, 12, 25, 33, 48, 77, 75, 90, 99 };
int BinaryFind(int vector[], int find)
{
      int g1,g2;
      int res, addr, newaddr;
      g1=0; g2=(SIZEVECTOR-1);
      addr=g1+(g2-g1)/2;
      while(1)
      {
            printf("%d index=%d\n",addr,vector[addr]);
            if(find==vector[addr]) return 1;
            else
                  if(find<vector[addr]) { if(g2>0) g2=addr-1;}
                  else { if(g1<SIZEVECTOR-1) g1=addr+1;}
            newaddr=g1+(g2-g1)/2;
            if(newaddr==addr) return 0;
            addr=newaddr;
      }//end while
}
void main()
{
      if(BinaryFind(vector,199)) printf("Find");
      else printf("don’t find\n");
      getch();
}