Reputation: 77
I was writing up code for a binary search algorithm.
Code:
#include "cs50.h"
int main(void) {
int n = GetInt();
int value = GetInt();
int values[n];
for (int i = 0; i < n; i++) {
printf("Put in number %i ", i + 1);
values[i] = GetInt();
}
int mid = (n - 1) / 2;
int en = 0;
int ex = n - 1;
for (int i = 0, xt = i + 1; i < xt; i++) {
if (value > values[mid]) {
en = mid;
mid = (en + ex) / 2;
}
else if (value < values[mid]) {
ex = mid;
mid = (en + ex) / 2;
}
else if (value == values[mid]) {
printf("found");
break;
} else {
printf("not found");
break;
}
}
}
But it only works when the value to be found is somewhere in the middle.
It fails when :
I really cannot figure out the mistake.
Upvotes: 3
Views: 520
Reputation: 5467
As others have mentioned, you have got your conditions wrong int the for
loop.
And one more issue is that
if (value > values[mid])
{
en = mid;
mid = (en+ex)/2;
}
here when (value > values[mid])
you are assigning mid to en
but instead mid+1
must be assigned as you have to search for the element after mid
similarly, when if (value < values[mid])
, ex
must be assigned with mid-1
as you have to search for element till the index 1
less than mid
A much better implementation of binary search would be the following:
Note: I have used
low
andhigh
instead ofen
andex
respectively
int mid; //no need to initialize as mid is initialized at the start of each iteration
int low = 0; //instead of en
int high = n-1; //instead of ex
while( low <= high )
{
mid = low + ((high - low) / 2);; //updating mid value
if (value > values[mid])
{
low = mid+1; //updating low
}
else if (value < values[mid])
{
high = mid-1; //updating high
}
else // if (value == values[mid])
{
printf("found"); //if found print 'found'
break;
}
}
if(low>high)
printf("not found\n");
making the above changes, your code would be:
#include "cs50.h"
#include <stdio.h>
int main(void)
{
int n = GetInt();
int value = GetInt();
if (n <= 0)
{
//handle the error or exit
}
int values[n];
for (int i=0;i<n;i++)
{
printf("Put in number %i \n",i+1);
values[i]=GetInt();
}
int mid;
int low = 0;
int high = n-1;
while( low <= high )
{
mid = low + ((high - low) / 2);
if (value > values[mid])
{
low = mid+1;
}
else if (value < values[mid])
{
high = mid-1;
}
else
{
printf("found");
break;
}
}
if(low>high)
printf("not found\n");
}
sample input:
5 //n
5 //value
1 2 3 4 5 //array elements
sample output:
Put in number 1
Put in number 2
Put in number 3
Put in number 4
Put in number 5
found
for further reading, read this : click
Upvotes: 2
Reputation: 59378
There are a bunch of little things you have to get right in a binary search: handle the length=0 case, make sure the position you test is always valid, make sure you don't overflow (i.e., `(low+high)/2' is not the best way to write that), make sure the new test position is always different from the previous one, etc.
After having done it like a million times, every binary search I write is now done just like this:
bool search(int array[], int length, int valueToFind)
{
int pos = 0;
int limit = length;
while(pos < limit)
{
int testpos = pos + ((limit - pos) >> 1);
if (array[testpos] < valueToFind)
pos = testpos + 1;
else
limit = testpos;
}
return (pos < length && array[pos] == valueToFind);
}
Notice that we only need to do one comparison per iteration, which is faster than the searches in the other answers. Instead of doing the equality test inside the loop, we reliably find the position where the element to find belongs, using only one comparison per iteration, and then at the end test to see if the element we want is there.
The way we calculate testpos
ensures that pos <= testpos < limit
, AND it works even if length is the largest possible integer value.
This form also makes it very easy to read off the invariants you want to see, without having to think about strange boundary conditions like high<low
. When you come out of the loop, pos==limit
so you don't have to worry about using the wrong one, etc.
The condition in this loop is also easily adaptable to different-purpose binary searches like "find where to insert x, ensuring that it goes after all the xs that are already in the array", "find the first x in the array", "find the last x in the array", etc.
Upvotes: 6
Reputation: 103
It seems to me that the for loop will only run 1 time
for(int i = 0, xt = i + 1; i < xt; i++) {}
Also for your binary search algorithm to work, your list of integers would need to be sorted. I'm not sure what GetInt() does exactly, but if it returns a random value, that would also cause the search to fail.
Upvotes: 2