Code for Binary search in C not working properly

Question

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

Answer 1

For starters for the number of elements of the array you shell use the type size_t. An object of the type int can be small to accommodate the number of elements in an array.

This condition of the loop

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

is incorrect. For example let's assume that the array has only one element. In this case high will be equal to 0 and hence equal to left due to its initialization

int high=size-1;

So the the loop will not iterate and you will get that the entered number is not found in the array though the first and single element fo the array actually will be equal to the number.

You need change the condition like

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

This if statement within the else statement

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

is redundant. You could just write

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

It would be better if the code that performs the binary search will be placed in a separate function.

Here is a demonstrative program that shows how such a function can be written.

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

Its output might look for example the following way

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

Answer 2

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

Answer 3

The problem is your while test. You have:

while(low<high) {
    ...
}

This will fail when low == high if the desired value is at that position. It is easily fixed by changing the test to:

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

This is all that's needed to fix it. You don't need to add any special cases to "fix it up". Just make sure your array is in ascending order and it should work.