Блог

Мой код не работает. Проблема может быть в цикле.Я пытался написать код на c для двоичного поиска, но он просто не выполняется.В информатике двоичный поиск, также известный как поиск с полуинтервалом, логарифмический поиск или двоичный поиск, представляет собой алгоритм поиска, который находит положение целевого значения в отсортированном массиве. Двоичный поиск сравнивает целевое значение со средним элементом массива.

 #include lt;iostreamgt; #include lt;stdio.hgt; using namespace std;  struct Array{  int A[20];  int length;  int size; };  int BinarySearch(struct Array arr,int key) {  int low=0;  int high=arr.length-1;  int mid=(low high)/2;    while(lowlt;=high) {  if(key==arr.A[mid])  return mid;    else if(keylt;arr.A[mid])  high=mid-1;    else  low=mid 1;   }   return -1;  }  int main() {  struct Array arr={{2,3,7,12,23,34,45,56,67,78,79,90,91,111,112,334,556,778,990,999},20,20};  coutlt;lt; BinarySearch(arr,7);   return 0; }  

Вы не настраиваете mid цикл, чтобы он оставался с тем же индексом, с которым вы его инициализировали.

Предлагаемое изменение:

 int BinarySearch(const Arrayamp; arr, int key) { // constamp;, no copy  int low = 0;  int high = arr.length - 1;  int mid;   while (low lt;= high) {  mid = (low   high) / 2; // assign mid inside the loop   if (key lt; arr.A[mid]) // Put the less than and greater than ...  high = mid - 1;  else if(arr.A[mid] lt; key) // ... comparisons first ...  low = mid   1;  else  return mid; // ... and let equal be the last  }   return -1; }  

Ставить сравнения «меньше» и «больше» перед проверкой «равно» предпочтительнее по двум причинам:

• Обычно это будет равнозначно false , поэтому первое сравнение других часто бывает более эффективным.
• Равные сравнения плохо работают с некоторыми типами, такими как типы с плавающей запятой.