[C++] Binary search

[ayu]

The principle of binary search is to cut the search area in half after every 'loop'


+
The positive part is that it's very fast since you cut the search area in half all the time.

-
Unfortunately the list has to be sorted.


Binary search

Code: Select all

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;
}

[xLeNaex]

I dont get any thing of which you posted HELP!?

[ayu]

I dont get any thing of which you posted HELP!?

Well have you learned any of the languages then, C/C++? or any programming language for that matter where you can implement this algorithm? =)

[Gogeta70]

Pretty smart cats Here's a php version because i was bored:

Code: Select all

<?PHP

function BinarySearch($list, $size, $value)
{
	$first = 0;
	$last = $size-1;
	$middle = 0;
	$pos = null;
	$found = FALSE;
	
	while(!$found && $first <= $last)
	{
		
		$middle = floor(($first + $last) / 2);
		
		if($list[$middle] == $value)
		{
			$found = TRUE;
			$pos = $middle;
		} else if($list[$middle] > $value)
		{
			$last = $middle - 1;
		} else {
			$first = $middle+1;
		}
		
	}
	
	return $pos;
	
	
}
?>

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.

[floodhound2]

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.

[leetnigga]

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:

Code: Select all

<?php
$middle = (int)(($first + $last) / 2)
?>

Saves a function call, too

[IceDane]

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.

[Gogeta70]

Well, what do ya know, i learned something new about php. Good call, leet.