Binary Search Vs Contains Functioning Inwards Coffee List

There are ii ways to search an chemical component subdivision inwards a List class, past times using contains() method or past times using Collections.binarySearch() method. There are ii versions of binarySearch() method, ane which takes a List in addition to Comparator in addition to other which takes a List in addition to Comparable. This method searches the specified listing for the specified object using the binary search algorithm. The listing must live on 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, in addition to 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 live on returned. This method runs inwards 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 in addition to is large, this method volition produce an iterator-based binary search that performs O(n) link traversals in addition to O(log n) chemical component subdivision comparisons. In the terminate this method returns the index of the search key, if it is contained inwards the list; otherwise, (-(insertion point) - 1).

The insertion betoken is defined equally the betoken at which the key would live on inserted into the list: the index of the origin chemical component subdivision greater than the key, or list.size() if all elements inwards the listing are less than the specified key.

This agency that render value volition live on >= 0 if in addition to solely if the key is found. Since mutual implementation of List interface e.g. ArrayList, Vector, CopyOnWriteArrayList and Stack implements RandomAccess interface, they tin hand the axe live on used for performing binary search, precisely at that topographic point are other implementations like LinkedList, which doesn't implement java.util.RandomAccess, so non suitable for binary search operation.

Since binary search tin hand the axe solely live on performed inwards sorted list, you lot too require to variety your collection earlier doing search, which may potentially touching on performance, peculiarly if your List is large in addition to non inwards sorted social club already.

Java Code for contains() Vs binarySearch()

Here is our programme to discovery object using binary search inwards Java List. We cause got a listing of Integer amongst 1M records in addition to uses both contains() in addition to 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 programme to perform binary search inwards 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 live on 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 hand the axe run across that contains() method is nigh 10 times faster than binary search, which agency it brand feel to run contains() for searching objects inwards 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 in addition to Algorithms: Deep Dive Using Java

Sumber https://javarevisited.blogspot.com/

Share this post