O(log n) algorithm

[_uj]

i agree with _uj

first try to create the BST then do a search right and left ..

Well, I didn't suggest a BST to be built In my reply #15 I suggested an O(log N) solution based on two slightly modified standard binary searches.

[ideru]

Well, I didn't suggest a BST to be built In my reply #15 I suggested an O(log N) solution based on two slightly modified standard binary searches.

oh okay my bad, you did not suggest a BST ..

but its good the OP can now have some options on how to solve the problem ..

[ideru]

There is absolutely no need for a BST here. As seeguna has shown you can perform O(log(n)) searches on arrays given the conditions of the problem easily. Complicating the issue with trees is not the solution.

If you look closely, the sample code that seeguna posted is actually a binary search code

[ProgramThis]

If you look closely, the sample code that seeguna posted is actually a binary search code

Yes, and you wouldn't have posted this comment if you knew the difference between a binary search and a binary search tree.

I was suggesting that there is no need to use a BST when you can perform a binary search on the array. YOU suggested placing the array into a BST and then using that. I was reasoning that there was no need to create the tree because a binary search can already be done on an array.