Friday 5 May 2017

Binary search on linked list in java

Before performing binary search operation on list:

  • Sort the given list in ascending order using sort(List) method. See the highlighted portion showing Collections.sort(javaRadarList); in the given program below.
  • After sorting, make call to binary search method. See the second highlighted method call Collections.binarySearch(javaRadarList"Spring"); Here first parameter is the list while the second one is the key that is to be searched in the specified list.


Note
If the list contain multiple elements that are equal to the specified object we are searching then there is no guarantee of which one will be found. Say we have multiple Spring object in list then search result will return which Spring index is not guaranteed.



Source fileSearchLinkedList

package javaRadarLinkedList;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class SearchLinkedList {

public static void main(String[] args) {
//create Linked List
LinkedList<String> javaRadarList = new LinkedList<String>();
//Add elements to LinkedList
javaRadarList.add("Java");
javaRadarList.add("Jquery");
javaRadarList.add("Spring");
javaRadarList.add("Hibernate");
javaRadarList.add("EJB");

//use iterator to traverse list
System.out.println("Before sorting: " +javaRadarList);

Collections.sort(javaRadarList); //sorting list element

Iterator<String> itrAfterSort = javaRadarList.iterator();
System.out.println("After Sorting:");
while(itrAfterSort.hasNext()){
String token = itrAfterSort.next();
System.out.println(token);
}

//Binary Search can be performed on Sorted List 
int i=Collections.binarySearch(javaRadarList, "Spring");
System.out.println("Given Key is present at index :"+ i +" on sorted list");

}

}



OUTPUT:

Before sorting: [Java, Jquery, Spring, Hibernate, EJB]
After Sorting:
EJB
Hibernate
Java
Jquery
Spring      //this Spring index(=4) is returned for binary search 
Given Key is present at index :4 on sorted list


To-do for readers:  Now try to add more than one Spring element in list and see the result on performing the binary search operation on the list.

Please write your opinion in the comment box about searching the element from the list using binary search mechanism. 


You may also like to read:



2 comments:

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
If you are looking for a reference book on java then we recommend you to go for → Java The Complete Reference
Click on the image link below to get it now.