tag:blogger.com,1999:blog-8712770457197348465.post1183183803961977270..comments2015-05-24T03:07:55.081-07:00Comments on Javarevisited: Binary Search vs Contains Performance in Java ListJavin Paulhttps://plus.google.com/114528699166048052030noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8712770457197348465.post-88876238126638723882015-05-15T22:34:34.267-07:002015-05-15T22:34:34.267-07:00Smit Jain is correct, there is no record in the li...Smit Jain is correct, there is no record in the list actually because list size is zero, therefore it never populates the list. <br />But here is catch, record time only for Collections.binarySearch(numbers, new Integer(1000000)); then only you will see the actual difference. The sorting is taking time and therefore you see different result from binary search. <br />Binary search is good only Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8712770457197348465.post-37661663864418832102015-05-15T22:02:29.221-07:002015-05-15T22:02:29.221-07:00Unfortunately this is a misleading article. You ca...Unfortunately this is a misleading article. You can not compare contains and binarySearch with just few records. Test both of them in 100k or million records then only you will see the actual difference.Anonymousnoreply@blogger.comtag: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