tag:blogger.com,1999:blog-6294663875929591018.post6726999071160953365..comments2019-05-04T12:02:05.782-07:00Comments on Ramblings of a techie: Given a sorted array, find k in least possible time in JavaBragBoyhttp://www.blogger.com/profile/01173019524783723568noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6294663875929591018.post-27188695677299041352013-10-28T02:57:08.743-07:002013-10-28T02:57:08.743-07:00@Faz - you are right.. good observation@Faz - you are right.. good observationBragBoyhttps://www.blogger.com/profile/01173019524783723568noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-15541740330700221972013-10-09T22:42:35.070-07:002013-10-09T22:42:35.070-07:00this is coded very similar to a binary search func...this is coded very similar to a binary search function. Fazhttps://www.blogger.com/profile/04986311100670591046noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-77810670822889501082011-12-14T04:20:14.992-08:002011-12-14T04:20:14.992-08:00@Pin-Sho Feng : Got it. Appreciate the link ! And ...@Pin-Sho Feng : Got it. Appreciate the link ! And yeah iteration and recursion always have trade off in terms of clarity, overhead and ease of understanding.<br /><br />Thanks for stopping by!bragadeeshhttps://www.blogger.com/profile/05516264230057880613noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-41125573222808604442011-12-14T03:30:51.842-08:002011-12-14T03:30:51.842-08:00By binary search I mean this:
http://en.wikipedia....By binary search I mean this:<br />http://en.wikipedia.org/wiki/Binary_search_algorithm<br /><br />In this case, an iterative version would be faster (in Java at least), avoiding some recursion overhead.Pin-Sho Fenghttps://www.blogger.com/profile/06177939263778008831noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-699831325431644062011-12-12T06:48:05.446-08:002011-12-12T06:48:05.446-08:00@Pin-Sho Feng : What do you mean by binary search ...@Pin-Sho Feng : What do you mean by binary search ? <br /><br />There is something called as binary search tree where you will first have to construct a BST which will take time more than O(n). Once its constructed, you can find the value in O(log n) time, <br /><br />But that is a different ballgame in this scenario. You will have to find k with least possible time which implicitly says you cannot waste any time at all.<br /><br />Hope I was clear. Let me know if you have any questions.bhttps://www.blogger.com/profile/01173019524783723568noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-20002737617246998222011-12-04T15:48:43.684-08:002011-12-04T15:48:43.684-08:00Isn't this just a regular binary search? Sorry...Isn't this just a regular binary search? Sorry if I'm missing something...Pin-Sho Fenghttps://www.blogger.com/profile/06177939263778008831noreply@blogger.com