Search code examples
carrayssortingif-statementbinary-search

Code for Binary search in C not working properly


I can't fix the logical error because I don't know what is wrong in this code. Every input, it shows "element not found". I would really appreciate it if someone can help me in this. Also in this code, I have assumed we'll be taking the size of the array as an odd number, what to do if we decide to take an even number as size?

#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;
}

Solution

  • EDIT: Refer to the better answer by @TomKarzes

    My old answer is:

    You missed a boundary case of high==low

    #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;
    }