CODEWITHSUNDEEP
cinfinite-loopbinary-search
Kat
Kat

Reputation: 678

C: Why does my binary search run into an infinite loop?

I have a program that searches a file (numbers.dat) using a binary search and prints whether the value is in the array or not. Currently, when I want to search for the first value in the numbers.dat file or for a value that is not in the numbers.dat file, I get an infinite loop, and if I want to search for any other value in the file it prints he index and Not found messages.

Here is my code:

 int main() {
     FILE *in_file; /* Input file */
     int middle;        /* Middle of our search range */
     int low, high; /* Upper/lower bound */
     int search;        /* number to search for */
     char line[80]; /* Input line */

     in_file = fopen(DATA_FILE, "r");
     if (in_file == NULL) {
          fprintf(stderr,"Error:Unable to open %s\n", DATA_FILE);
          exit (8);
     }

     /*
      * Read in data
      */

     max_count = 0;
     while (1) {
          if (fgets(line, sizeof(line),  in_file) == NULL)
          break;

          /* convert number */
          sscanf(line, "%d", &data[max_count]);
          ++max_count;
     }

    while (1) {
        printf("Enter number to search for or -1 to quit:" );
        fgets(line, sizeof(line), stdin);
        sscanf(line, "%d", &search);

        if (search == -1)
            break;

       low = 0;
        high = max_count;

       while (1) {
             middle = (low + high) / 2;

         if (data[middle] == search) {
         printf("Found at index %d\n", middle);

         }

         if (low == high) {
         printf("Not found\n");
         break;
         }

         if (data[middle] < search)
         low = (middle + 1);
         else
         high = (middle - 1);
     }
    }
     return (0);
}

The numbers.dat file's first few lines are: 4 6 14 16 17 And if I search for 4 or say 2, I get an infinite loop and if I search for 6 I get:
Found at index 1
Not found

Upvotes: 0

Views: 521

Answers (2)

Joel Lee
Joel Lee

Reputation: 3864

The following code:

   while (1) {
         middle = (low + high) / 2;

     if (data[middle] == search) {
     printf("Found at index %d\n", middle);

     }

Does not exit the loop. Figure out what you need to do to get out of that.

Upvotes: 1

MByD
MByD

Reputation: 137372

  1. You should break with not found if low > high.
  2. You don't break if you found, so you go to another iteration.
  3. You always check for middle. what if high or low have the needed result?

Upvotes: 4

Related Questions