Question

Observe the things at Home in which you are using binary
conditions

Answer 1

Answer:

===>The Ubiquitous Binary Search | Set 1

We all aware of binary search algorithm. Binary search is easiest difficult algorithm to get it right. I present some interesting problems that I collected on binary search. There were some requests on binary search.

I request you to honor the code, “I sincerely attempt to solve the problem and ensure there are no corner cases”. After reading each problem minimize the browser and try solving it.

Problem Statement: Given a sorted array of N distinct elements. Find a key in the array using least number of comparisons. (Do you think binary search is optimal to search a key in sorted array?)

Without much theory, here is typical binary search algorithm.

// Returns location of key, or -1 if not found

int BinarySearch(int A[], int l, int r, int key)

{

int m;

while( l <= r )

{

m = l + (r-l)/2;

if( A[m] == key ) // first comparison

return m;

if( A[m] < key ) // second comparison

l = m + 1;

else

r = m - 1;

}

return -1;

}

Theoretically we need log N + 1 comparisons in worst case. If we observe, we are using two comparisons per iteration except during final successful match, if any. In practice, comparison would be costly operation, it won’t be just primitive type comparison. It is more economical to minimize comparisons as that of theoretical limit.