Код для двоичного поиска в C не работает должным образом

Question

Я не могу исправить логическую ошибку, потому что я не знаю, что не так в этом коде. Каждый вход показывает «элемент не найден». Я был бы очень признателен, если бы кто-то мог помочь мне в этом. Также в этом коде я предположил, что мы будем принимать размер массива как нечетное число, что делать, если мы решим взять четное число как размер?

#include<stdio.h>
int main(){
  int size;
  printf("Enter the number of elemets(odd number) : ");
  scanf("%d",&size);
  int arr[size];
  printf("Enter the elements in ascending order : ");
  for(int i=0;i<size;i++){
    scanf("%d",&arr[i]);
  }
  int element;
  int flag=0;
  printf("Enter element to be found : ");
  scanf("%d",&element);
  int low=0;
  int high=size-1;
  while(low<high){
    int mid=(low+high)/2;

    if(element<arr[mid]){
      high=mid-1;
    }
    else if(element>arr[mid]){
      low=mid+1;
    }
    else if(element==arr[mid]){
      printf("Element %d found at pos %d ",element,mid);
      flag=1;
      break;
    }
  }
  if(flag==0){
    printf("Element not found");
  }

  return 0;
}

Answer 1

Проблема в вашем while тесте. У вас есть:

while(low<high) {
    ...
}

Это произойдет сбой при low == high, если желаемое значение находится в этой позиции. Это легко исправить, изменив тест на:

while(low <= high) {
    ...
}

Это все, что нужно, чтобы это исправить. Вам не нужно добавлять какие-либо особые случаи, чтобы "исправить это". Просто убедитесь, что ваш массив находится в порядке возрастания, и он должен работать.

Answer 2

РЕДАКТИРОВАТЬ: См. Лучший ответ @TomKarzes

Мой старый ответ:

Вы пропустили граничный случай высокого == низкий

#include<stdio.h>
int main(){
  int size;
  printf("Enter the number of elements(odd number) : ");
  scanf("%d",&size);
  int arr[size];
  printf("Enter the elements in ascending order : ");
  for(int i=0;i<size;i++){
    scanf("%d",&arr[i]);
  }
  int element;
  int flag=0;
  printf("Enter element to be found : ");
  scanf("%d",&element);
  int low=0;
  int high=size-1;
  while(low<high){
    int mid=(low+high)/2;

    if(element<arr[mid]){
      high=mid-1;
    }
    else if(element>arr[mid]){
      low=mid+1;
    }
    else if(element==arr[mid]){
      printf("Element %d found at pos %d ",element,mid);
      flag=1;
      break;
    }
  }
  if(low==high && arr[low]==element) //Added 1 extra condition check that you missed
  {
    printf("Element %d found at pos %d ",element,low);
    flag=1;
  }
  if(flag==0){
    printf("Element not found");
  }

  return 0;
}

Answer 3

Для начала для количества элементов массива, который вы используете, используйте тип size_t. Объект типа int может быть небольшим, чтобы вместить количество элементов в массиве.

Это условие l oop

int high=size-1;
while(low<high){
//...

неверно. Например, давайте предположим, что массив имеет только один элемент. В этом случае high будет равно 0 и, следовательно, равно left из-за его инициализации

int high=size-1;

Таким образом, l oop не будет повторяться, и вы получите, что введенное число равно не найден в массиве, хотя первый и единственный элемент массива фактически будет равен числу.

Вам необходимо изменить условие следующим образом:

while ( !( high < low ) )
//...

Этот оператор if внутри оператора else

else if(element==arr[mid]){

является избыточным. Вы могли бы просто написать

else // if(element==arr[mid]){

Было бы лучше, если бы код, который выполняет бинарный поиск, был помещен в отдельную функцию.

Вот демонстрационная программа, которая показывает, как такая функция можно записать.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int binary_search( const int a[], size_t n, int value )
{
    size_t left = 0, right = n;  
    int found = 0;

    while ( !found && left != right )
    {
        size_t middle = left + ( right - left ) / 2;

        if (  value < a[middle] )
        {
            right = middle;
        }
        else if ( a[middle] < value )
        {
            left = middle + 1;
        }
        else
        {
            found = 1;
        }
    }

    return found;
}

int cmp( const void *a, const void *b )
{
    int left  = *( const int * )a;
    int right = *( const int * )b;

    return ( right < left ) - ( left < right );
}

int main(void) 
{
    const size_t N = 15;

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < N; i++ )
    {
        size_t n = rand() % N + 1;

        int a[n];

        for ( size_t j = 0; j < n; j++ ) a[j] = rand() % N;

        qsort( a, n, sizeof( int ), cmp );

        for ( size_t j = 0; j < n; j++ )
        {
            printf( "%d ", a[j] );
        }
        putchar( '\n' );

        int value = rand() % N;

        printf( "The value %d is %sfound in the array\n",
                value, binary_search( a, n, value ) == 1 ? "" : "not " );
    }

    return 0;
}

Его вывод может выглядеть, например, следующим образом

0 2 2 3 4 5 7 7 8 9 10 12 13 13 
The value 5 is found in the array
4 8 12 
The value 10 is not found in the array
1 2 6 8 8 8 9 9 9 12 12 13 
The value 10 is not found in the array
2 3 5 5 7 7 7 9 10 14 
The value 11 is not found in the array
0 1 1 5 6 10 11 13 13 13 
The value 7 is not found in the array
0 3 3 3 4 8 8 10 11 12 14 14 14 14 
The value 3 is found in the array
0 5 5 10 11 11 12 13 13 14 14 
The value 12 is found in the array
3 4 5 7 10 13 14 14 14 
The value 14 is found in the array
0 3 3 7 
The value 2 is not found in the array
1 6 9 
The value 10 is not found in the array
2 2 3 3 4 4 4 5 5 6 8 8 9 13 13 
The value 11 is not found in the array
11 11 13 
The value 11 is found in the array
0 0 0 1 2 5 5 5 7 7 8 9 12 12 14 
The value 6 is not found in the array
8 8 13 
The value 1 is not found in the array
2 2 4 4 5 9 9 10 12 12 13 13 14 14 
The value 14 is found in the array