Corey Ford Corey Ford - 10 days ago 6
C Question

Modified Binary Search Array

EDIT: included improved code.

My current logic is incorrect. I want to have a binary search that will find the integer "wantToFind", and if it is not in the array will subtract 1 from wantToFind until it is found.

I have subtracted this from a larger program, that guarantees that the 1st item in the array will be the lowest wantToFind (the value we want to find) can ever be.

However, despite following binary search conventions the program is still getting stuck when looking for higher numbers such as 88.

float list[15] = {60,62,64,65,67,69,71,72,74,76,77,79,81,83,84};

//binary search
int wantToFind = 88; //other tests are 65, 61, 55
bool itemFound = false;

int current = 0;
int low = 0;
int high = 14;

current = (low+high)/2;
//int previousCurrent = -1;

do {
do {
//if 61 < 72
if (wantToFind < list[current])
{
//smaller
//previousCurrent = current;
high = current - 1;
current = (low+high/2);
}
else if (wantToFind > list[current])
{
//bigger
//previousCurrent = current;
low = current + 1;
current = (low+high/2);
}
else{
if(wantToFind == list[current])
{
itemFound = true;
}
}

} while (low >= high);

if (itemFound == false)
{
wantToFind--;
}
} while (itemFound == false);

printf("\n%d", wantToFind); //which will be a number within the list?
return 0;


}

Answer

I can't imagine why you'd want while (low >= high). This will cause the loop to terminate the first time through. I'm pretty sure you want while (low <= high).

Also, when the item isn't found, there are three possibilities:

  1. wantToFind is smaller than the smallest item in the list.
  2. wantToFind is larger than the largest item in the list.
  3. wantTofind would be located somewhere in the list.

In cases 2 and 3, the value of current when the inner loop exits will be one more than the index that contains the first item smaller than wantToFind.

In case 1 above, current will be equal to 0.

The point is that there's no need for the outer loop. When the binary search fails, the value of current tells you the insertion point.

Also, you probably want to early-out when the item is found.

Finally, do yourself a favor and turn that do...while into a while loop. That is:

while (!itemFound && low <= high)

You'll find that a lot easier to reason about.

Comments