Binary Search

this is an very good tutorial about binary search in the topcoder

General algorithm:

Finding a value in a sorted sequence:

binary_search(A, target):
  lo = 1, hi = size(A)
  while lo <= hi:
     mid = lo + (hi-lo)/2
     if A[mid] == target:
        return mid            
     else if A[mid] < target:
        lo = mid+1
     else:
        hi = mid-1
           
  // target was not found

Upper Bound:

Return iterator to upper bound

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

C++ STL - upper_bound()

Lower Bound:

Return iterator to lower bound

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

C++ STL - lower_bound()

Binary_Search :

Returns true if any element in the range [first,last) is equivalent to val, and false otherwise.
C++ STL - binary_search()

Implementing upper_bound and lower_bound :
While implementing upper_bound or lower_bound on your ownself may arises some tedious problems. Such as depending on your implementation the ans can be sometimes in the low pointer and sometimes in the high pointer. It was a very disturbing thing. Then one day my coach has given me an amazing solution of this problem. It's kindaa generic. So remembering it won't be an issue.

lower_bound:

int low=0,high=n;
while(low<=high)
{
int mid = (low + high ) / 2;

if(arr[mid]>=x) high = mid -1;          ///so at first try to eliminate the second portion and do not break                                                                 if equal
else
low = mid + 1;
}

If you implement this method the answer will always be in low pointer.
P.S: sometimes you may need to check one more time if the low actually is the answer, in case of not found.

upper_bound:

int low=0,high=n;
while(low<=high)
{
int mid = (low + high ) / 2;

if(arr[mid]<=x) low = mid + 1;          ///so at first try to eliminate the first portion and do not break                                                                      if equal
else
high = mid -1;

}

And most amazingly in this method of implementation the answer will also be in the low pointer. :) quite easy i guess. Thanx to Mr. forthright48 for this amazing solution. :)