Блог

Я создавал эту функцию двоичного поиска на языке си, но столкнулся с проблемой. Я передал указатель отсортированного массива, его (размер-1) и номер, который нужно найти. Когда я пытаюсь сравнить значения в передней позиции и последней позиции в цикле while, это не работает для значений справа от среднего элемента. Например, если я передаю массив={1,2,3,4,5} для {1,2,3}, функция работает нормально, однако для {4,5} цикл выполняется только один раз и завершается. Есть еще одна проблема, эта проблема возникает только в том случае, если мы сравниваем значения адресов указателей, но если вместо этого я сравниваю указатели, функция работает идеально. Лучше объяснено в приведенном ниже коде.

 int binarysearch(int*p,int r,int num){  //p is pointer of an array, r is the (sizeof(array)-1), num is the number to be searched  int *mid;  while(*plt;=*(p r)){//if we replace the condition with(plt;=(p r)) the function works  mid=(p (r/2));  printf("1 ");  if(*mid==num)  return *mid;  if(*midlt;num)  p=mid 1;  else  r=((r/2)-1);   }  return -1; }  

Проверьте, как вы рассчитываете mid значение.

В первой итерации, mid=(p (r/2)) даст вам средний срок правильно. Пусть, скажем, r=5, и что на первой итерации мы получили *midlt;num так, что теперь p=mid 1 или p=p 3. Проблема сейчас в том, что r по-прежнему равен 5, поэтому указатель массива просто сместился от своих значений, не отметив новый конец. Это может легко привести к ошибке сегментации, если вы попытаетесь использовать свой адрес результата позже.

решение простое: не вычисляйте mid положение с помощью указателя и int. Используйте два указателя, чтобы пометить вышибалы поиска, или два целых числа, чтобы пометить их индексы. Вы также можете использовать свой способ, но не забывайте обновлять размер r каждую итерацию.

Первый вариант — использование индексов (мой выбор, если бы мне пришлось их сделать):

 int binarysearch(int*p,int r,int num){  int mid;  int a=0;  while(alt;=r) {  mid=(a r)/2;  printf("1 ");  if(p[mid]==num)  return *mid;  else if(p[mid]lt;num)  a=mid 1;  else if(a==r)  break;  else  r=mid;  }  return -1; }  

Второй вариант — ваша исправленная версия:

 int binarysearch(int*p,int r,int num){  int *mid;  while(rgt;=0) {  mid=p (r/2);  printf("1 ");  if(*mid==num)  return *mid;  else if(*midlt;num) {  p=mid 1;  r-=(r/2) 1;  }  else if (r==0)  break;  else  r/=2;  }  return -1; }