Issue about Binary search algorithm in c

Question

I am confused in understating the behavior of the code while searching for an element which does not exist in the array.

1. The result of the element index i am looking for is always zero while declaring it as int index;.
2. The result of the element index i am looking for is random number while declaring it as size_t index; what is the difference between declaring the variable index as int index; andsize_t;in the code below.

The code

#include <stdio.h>
#define SIZE 5
int main(void)
{
    int numbers[SIZE]={1,2,3,4,5};
    int search =0; // This variable define the required number i am searching for 
    int start = 0 ;
    int end = SIZE-1 ;
    size_t index;
    while (start <= end)
    {
        int middle = (start+end)/2;
        if  (search == numbers[middle])
        {
            index = middle;
        }
        if (search > numbers[middle])
        {
            start = middle+1 ;
        }
        else
        {
            end= middle-1 ;
        }
    }
    printf("The index of the element is %d",index);
return 0;
}

Answer 1

The basic problem is that index is not initialized and that it never gets assigned when you don't find what you are searching for. Since the printf statement accesses an uninitialized variable in that case, your code have undefined behavior, i.e. anything may happen - including print of all sorts of numbers.

The result of the element index i am looking for is always zero while declaring it as int index;

That is "just by luck"

The result of the element index i am looking for is random number while declaring it as size_t index;

That is also "just by luck"

Answer 2

You are not using correct specifier for size_t, it's not %d.

Try to use %zd or %ld and it'll work fine.

Furthermore, add this after the while loop so that it doesn't show weird value of index when the element is not present in the array.

if(start>end) {
   printf("That number is not present in the array");
   return 0;
}

And move the line printf("The index of the element is %d",index); under the condition if (search == numbers[middle]). So that you don't get "this number is not present" even if it is present in the array. For corrected version of your code see https://code.hackerearth.com/80043dg?key=7b325b26aec0f5425b76cc3efbdc93cf

Answer 3

Here are a couple of action items you can take to improve your code:

1. Since this array is statically defined there is no need to include the SIZE define inside the []. Declare it like this int numbers[]={1,2,3,4,5}; instead of this int numbers[SIZE]={1,2,3,4,5};. Let the compiler do the math for you.
2. Initialize index to some value (i.e. index = 0;). this is the main cause of the problem and it is introducing undefined behavior to the program.
3. Change the type of size_t index to int index every variable that was declared in the program is an int and the program is treating index as an int. So it might as well be an int to avoid confusion.

4. Make this an else if clause instead of just an if:

   else if (search > numbers[middle])
   {
       start = middle+1 ;
   }   
   

5. Add another case to have the program fail gracefully when the value to be searched is missing from the data set. Such as, printf("Data not found: %d", search);

The algorithm still isn't 100% and has some flaws but I will leave this up to you to figure out. I hope this info helps!

Best Regards!

Answer 4

The problem is that , the value of indexis not initialized.

initializing the variable to 0 does not solve your problem. Because you are using index to return the position of the array element.

By initializing the index = 0 will provide he same result for the elements not present in the array as well as the for the first element to the of the array .

The better way is to initialize as size_t index = -1;

So that the result for the elements not present in the array would b -1.

Also check for the access specifier used in the printf statement, for size_t datatype. It can be ,

printf("The index of the element is %ld",index);