# Optimize binary serach...

Discussion in 'C' started by asadullah.ansari, Jan 20, 2009.

Joined:
Jan 9, 2008
Messages:
356
14
Trophy Points:
0
Occupation:
Developer
Location:
NOIDA
All of you alraedy know the binary search..I need not to explain that algorithm...
we know that there are two compariosions one for greater than mid value and other is for less than mid value. Optimize this algorithm/program so that only one comparision shoul happened in that algorithm?

Note: binary search means not a binary serch tree.... BST algorithm is totally different that Binary Serch algorithm.

Joined:
Jan 9, 2008
Messages:
356
14
Trophy Points:
0
Occupation:
Developer
Location:
NOIDA
Now i want to make this problem more clear...
binary serach algo is as:
Code:
BinarySearch(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)             ///First check
high = mid - 1
else if (A[mid] < value)       //second check
low = mid + 1
else
return mid // found
}
}
In a while loop there is two check(if condition) ...You have to reduce it by one inside while loop.

Last edited by a moderator: Jan 20, 2009

Joined:
Aug 6, 2004
Messages:
3,009