int BinarySearch(int list[], int size, int value)
{
int first = 0;
int last = size - 1;
int middle = 0;
int position = -1;
bool found = false;
while(!found && first <= last)
{
/*
The middle position is equal to the first one plus
the last one divided by two.
Example: if we have an array list[10]
and, first = 0, last = size - 1 (9)
then middle = (0 + 9) / 2
which is 4.5, but since this is an integer division
the 5 is simply cut off, which means that
the position in this case is 4.
*/
middle = (first + last) / 2;
if(list[middle] == value)
{
found = true;
position = middle;
}
/*
Decide if which "half" of the list to remove
*/
else if(list[middle] > value)
last = middle - 1;
else
first = middle + 1;
}
return position;
}
I added the floor() function in because in php variable types are automatically converted from integer to float - unlike in C/C++. Using the floor function returns the same result that cats' version does, it drops the decimal and just gives you the integer.
gogeta70 wrote:I added the floor() function in because in php variable types are automatically converted from integer to float - unlike in C/C++. Using the floor function returns the same result that cats' version does, it drops the decimal and just gives you the integer.
For a solution more similar to cats' you could cast the result to an integer:
floodhound2 wrote:Cats, could you give us an example of when a programmer would want to implement this?
It seems to me that if you wanted to look up something from a table you would just simply start at one end until you reach the answer or the end.
Think massive lists, and think about what happens if the element isn't there.
In the case that the element is there, it will be found in O(log n). If the element isn't there, then that will be determined in O(log n) as well. That beats O(n) for both cases.