Binary Search

This is how binary search works, and this how you will find it written in most popular books.This one is straight out of Wikipedia.

low = 0

high = N

while (low <>

mid = (low + high) / 2

if (A[mid] <>

low = mid + 1;

else

//can't be high = mid-1: here A[mid] >= value,

//so high can't be <>

high = mid;

}

// high == low, using high or low depends on taste

if ((low <>

return low // found

else

return -1 // not found

It feels perfect, looks perfect even the Prof in your class must have written the same, then why am I talking about it. Well ,it has a major bug which had stayed undetected like for ever and detected sometime very recently. (Google for more details and timeline)

Problem: Well line 4 says, mid=(high+low)/2.Say if "high" is the highest integer your compiler can access and if low is any number greater than zero then mid goes out of range and causes overflow problems. :O :O

Solution: Do (high/2 +low/2) or low+(high-low)/2

Come to think of it: While implementing many other array based divide and conquer algorithms like merge sort etc, we do the same to get to the center of the array.

Caution :Don't take the average.