BINARY SEARCHES

A binary search can be performed on an ordered array. It works by taking a value
that is being searched for and testing it by the element in the middle of the array. If
the value being searched for is lower than the item in the middle of the ordered
array, it can be determined that if the value exists, it is in the first half of the array.
If the value is larger than the element in the middle, the value might exist in the
upper half. Once the direction is known, half of that new section is tested to further
narrow down where the value can be. This is repeated until the value is found or
until there are no more elements left. The binary search gets its name from the fact
that the remaining elements are always split in half (binary equals 2). Because a binary search requires the elements to be in order, this algorithm cannot work for an unordered array since the
unordered array can be unpredictable in terms of item positions.
The binary search can eliminate large sections of an array in an effort to narrow
down the list to find the value, assuming it exits. When compared to the linear
search, this can result in a huge difference in performance as Ngrows larger. For example, an array being searched with a linear algorithm that is made up of 1 million
elements will take on average 500,000 steps for items that exist, which can mean
that some checks can go up to the whole million depending on the item. Using a
binary search on an ordered array with that same number of elements will take
20 comparisons. To go from an average of 500,000 comparisons to just 20 is a huge
difference. To go from 1 million comparisons to 20 with items that are not found


while(1)
{
current = (lowerBound + upperBound) >> 1;
if(m_array[current] == searchKey)
{
return current;
}
else if(lowerBound > upperBound)
{
return -1;
}
else
{
if(m_array[current] < searchKey)
lowerBound = current + 1;
else
upperBound = current - 1;
}
}
return -1;
}
};


The binary search  starts off by defining the bounds that make up
the search range, which is initially set to the entire array. Once the range is set, the
middle of the range is determined and the element at the position is tested. If the
item is found, the index is returned; if the lower bound’s value becomes higher than
the upper bound’s value (which will happen when the search has stepped through
the entire array), then the value is not found. If neither of these two cases are true,
the lower bound, which is the minimum search range position, is adjusted if
the item is greater than the item in the middle, or else the upper bound is adjusted.
Adjusting the range values will quickly shrink the search range until the value is
found or until there are no more elements to check this

operation is pretty fast as N grows larger.