tag:blogger.com,1999:blog-8712770457197348465.post1183183803961977270..comments2014-08-22T02:03:57.146-07:00Comments on Javarevisited: Binary Search vs Contains Performance in Java ListJavin Paulhttps://plus.google.com/114528699166048052030noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-8712770457197348465.post-82354912607386463862014-04-01T23:01:53.583-07:002014-04-01T23:01:53.583-07:00I don't agree "contains() method is almos...I don't agree "contains() method is almost 10 times faster than binary search" infact the binary search is always many times faster than contains()<br />Reason : contains uses traditional linear search algorithm so the complexity is O(n) whereas the Binary search has complexity of O(logn).<br /><br />Your code is giving incorrect result because the list (numbers) you are filling is Smit Jainhttp://www.blogger.com/profile/09321023229126364700noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-80125559453154797322014-03-27T10:20:24.992-07:002014-03-27T10:20:24.992-07:00Well, I think that this is not fare relatively to ...Well, I think that this is not fare relatively to binarySearch() as you measure it's time in conjunction with sorting invocation which takes additional O(NlogN) time. It would be more convenient if you test these methods on a sorted list or take a timestamp not before sorting a list but just before invoking of binarySearch(). You will get antipodal results.AlexBonelhttp://www.blogger.com/profile/17251533675581407202noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-42367861098341706962014-03-26T04:14:12.517-07:002014-03-26T04:14:12.517-07:00@Anonymous: if you check the source code of ArrayL...@Anonymous: if you check the source code of ArrayList, contains method internally call indexOf method only. So time for both of them will same. I think. (other than a extra method call.)<br /><br />This is a good tutorial. <br />Additional info: time complexity of contains and binarySerach depends on the given list. If it is already ordered list, i will go for BinarySearch(which will take O(logn)Prasenhttp://www.blogger.com/profile/12386267115603693558noreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-58086407921724276002014-03-25T03:20:06.920-07:002014-03-25T03:20:06.920-07:00for searching in a list., we can indexOf() also, T...for searching in a list., we can indexOf() also, This gives better timing than contains()..<br /><br />correct me if I am wrong...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-36485295440987875382014-03-23T21:52:47.880-07:002014-03-23T21:52:47.880-07:00I would do the sorting prior start time to be more...I would do the sorting prior start time to be more justified.<br />But yes "contains ' is faster then "binarySearch" for ArrayList,<br />Below my output :<br />Time to search 1Mth Record using contains() is {} nano seconds 84585<br />Time to search 1Mth Record using binary search is {} nano seconds 1283703<br />Abhishek Kapoorhttp://www.blogger.com/profile/13797823134112342051noreply@blogger.com