Corey Ford - 11 months ago 53

C Question

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 Source

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:

`wantToFind`

is smaller than the smallest item in the list.`wantToFind`

is larger than the largest item in the list.`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.