Binary Search Vs Contains Functioning Inwards Coffee List

There are 2 ways to search an chemical ingredient inward a List class, past times using contains() method or past times using Collections.binarySearch() method. There are 2 versions of binarySearch() method, ane which takes a List together with Comparator together with other which takes a List together with Comparable. This method searches the specified listing for the specified object using the binary search algorithm. The listing must hold upward sorted into ascending social club according to the natural ordering of its elements (as past times the sort(List) method) prior to making this call. If List is non sorted, so results are undefined. If the List contains multiple elements equal to the specified object, at that topographic point is no guarantee which ane volition hold upward returned. This method runs inward log(n) fourth dimension for a "random access" listing (which provides near-constant-time positional access).

If the specified listing does non implement the RandomAccess interface together with is large, this method volition produce an iterator-based binary search that performs O(n) link traversals together with O(log n) chemical ingredient comparisons. In the destination this method returns the index of the search key, if it is contained inward the list; otherwise, (-(insertion point) - 1).

The insertion indicate is defined equally the indicate at which the key would hold upward inserted into the list: the index of the outset chemical ingredient greater than the key, or list.size() if all elements inward the listing are less than the specified key.

This agency that render value volition hold upward >= 0 if together with exclusively if the key is found. Since mutual implementation of List interface e.g. ArrayList, Vector, CopyOnWriteArrayList and Stack implements RandomAccess interface, they tin hold upward used for performing binary search, merely at that topographic point are other implementations like LinkedList, which doesn't implement java.util.RandomAccess, thence non suitable for binary search operation.

Since binary search tin exclusively hold upward performed inward sorted list, you lot equally good necessitate to form your collection earlier doing search, which may potentially behaviour upon performance, peculiarly if your List is large together with non inward sorted social club already.

Java Code for contains() Vs binarySearch()

Here is our plan to uncovering object using binary search inward Java List. We get got a listing of Integer alongside 1M records together with uses both contains() together with binarySearch() method to search an element.

import java.util.ArrayList; import java.util.Collections; import java.util.List; import org.slf4j.Logger; import org.slf4j.LoggerFactory;  /**    * Java plan to perform binary search inward Java collection e.g List, Set   * @author Javin Paul   */ public class BinarySearchTest {     public static final Logger logger = LoggerFactory.getLogger(BinarySearchTest.class);         public static void main(String args[]) {                   //creating List         List<Integer> numbers = new ArrayList<Integer>(1000000); //List of 1M records                 //initializing List         for(int i =0; i<numbers.size(); i++){             numbers.add(new Integer(i));         }                //performing contains search         long startTime = System.nanoTime();         boolean isExist = numbers.contains(new Integer(1000000));         long totalTime = System.nanoTime() - startTime;                        logger.info("Time to search 1Mth Record using contains() is {} nano seconds", totalTime);                 //performing binary search         startTime = System.nanoTime();         Collections.sort(numbers);  // List needs to hold upward sorted for Binary Search         Integer release = Collections.binarySearch(numbers, new Integer(1000000));         totalTime = System.nanoTime() - startTime;                 logger.info("Time to search 1Mth Record using binary search is {} nano seconds", totalTime);     }    }  Ouput: 2013-06-04 23:23:17,834 0    [main] INFO  test.BinarySearchTest  - Time to search 1Mth Record using contains() is 51404 nano seconds 2013-06-04 23:23:17,849 15   [main] INFO  test.BinarySearchTest  - Time to search 1Mth Record using binary search is 554261 nano seconds
 

From the output, you lot tin run across that contains() method is nigh 10 times faster than binary search, which agency it brand feel to purpose contains() for searching objects inward List, peculiarly for those which implements RandomAccess interface e.g. ArrayList.

Further Learning
Java In-Depth: Become a Complete Java Engineer
Java Fundamentals: Collections
Data Structures together with Algorithms: Deep Dive Using Java

Share this post