O(log n) algorithm

Quote:

---

Originally Posted by ideru

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.

Quote:

---

Originally Posted by _uj

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 ..:rolleyes:

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

Quote:

---

Originally Posted by ProgramThis

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 :)

Quote:

---

Originally Posted by ideru

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.