Actual complexity of above algorithm = O(n^1.6)
On Sep 27, 8:19 am, Gene gene.ress...@gmail.com wrote:
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2)
I feel the binary search approach as given by Saurabh Singh or like
moving from top right row, doing binary search in the row 0, find the
element being searched (say x) or one less than that (say y), followed
by binary search in the column below 'y' and proceeding in this way
can give a less than
Well, friend, we're both wrong.
The algorithm will find 6 just fine. It will choose 3 as the middle
element. Since 6 is bigger, it will throw away the subarray
1 2
2 3
and check the other 3 subarrays. When it checks
6 7
7 8
It will find the 6 on the first try. I just verified this by
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2) The element you're looking for is smaller. In this case you can
throw out about 1/4 of the array: everything
