CODEWITHSUNDEEP
calgorithmsearchruntime-errorbinary-search
Colin Rickels
Colin Rickels

Reputation: 109

Binary search with C

I understand the concept pretty throughly oh how the binary search works and what needs to take place, yet when attempting to implement with C, the search has not yet once been successful. I could really use a well given explanation of where my error exists and why it is error prone as well as the proper way to re-write it. This is not a homework assignment I would like to point out but just a topic that has to be applied throughly for me to pass Computer Science II. Here is the code.

#include<stdio.h>

int main(int argc, char** argv) {       
    int array[11] = {11,24,47, 57,58,59,89,94,102,150,250};

    int n = sizeof(array)/4;             
    int key;                         

    int topIndex = n-1;        
    int bottomIndex = 0;        

    int middleIndex = (topIndex + bottomIndex) / 2; 

    printf("%d is the initial middle index position which contains the integer %d\n\n", middleIndex, array[middleIndex]);

    scanf("%d", &key);
    printf("%d was read in, i will now search for the number\n\n", key);

    while(bottomIndex<=topIndex)
    {
        if(key==array[middleIndex])
        {
          printf("I found %d in %d\n\n", key, middleIndex);
          break;
        }
        else if(key<array[middleIndex])
        {
            topIndex = middleIndex-1;
            middleIndex = (topIndex + bottomIndex) / 2;
            printf("Middle Index: %d , Top Index: %d , Bottom Index: %d\n\n", middleIndex, topIndex, bottomIndex);

        }

    }


    return 0;
}

Upvotes: 3

Views: 97

Answers (2)

CIsForCookies
CIsForCookies

Reputation: 12817

Your are on your way.

else if(key<array[middleIndex])
{
    topIndex = middleIndex-1;
    middleIndex = (topIndex + bottomIndex) / 2;
    printf("Middle Index: %d , Top Index: %d , Bottom Index: %d\n\n", middleIndex, topIndex, bottomIndex);

}

This section handles the case where your key is smaller then the middle position in the array. Now handle the other case:

else if(key>array[middleIndex])
{
    bottomIndex = middleIndex;
    middleIndex = (topIndex + bottomIndex) / 2;
    printf("Middle Index: %d , Top Index: %d , Bottom Index: %d\n\n", middleIndex, topIndex, bottomIndex);

}

Upvotes: 2

Marco A.
Marco A.

Reputation: 43662

You're not moving the bottomIndex when the key is more than the value at middleIndex. A fixed version follows

while (bottomIndex <= topIndex)
{
  if (key == array[middleIndex])
  {
    printf("I found %d in %d\n\n", key, middleIndex);
    break;
  }
  else if (key<array[middleIndex])
    topIndex = middleIndex - 1;
  else
    bottomIndex = middleIndex + 1; // This part was lacking

  // This code is common to both cases above
  middleIndex = (topIndex + bottomIndex) / 2;
  printf("Middle Index: %d , Top Index: %d , Bottom Index: %d\n\n", middleIndex, topIndex, bottomIndex);
}

Upvotes: 1

Related Questions