Java Program to Compare Binary and Sequential Search

«
»
This is a java program to compare Binary Search and Linear Search algorithms. Following class provides the time required to search an element for both the algorithms

Here is the source code of the Java Program to Compare Binary and Sequential Search. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This the the java program to compare the sequential and binary search
  2. import java.util.Random;
  3. import java.util.Scanner;
  4.  
  5. public class Sequential_Binary_Compare 
  6. {
  7.     public static int N = 1000;
  8.     public static int[] sequence = new int[N];
  9.  
  10.     public static boolean sequentialSearch(int[] sequence, int key) 
  11.     {
  12.         for (int i = 0; i < sequence.length; i++)
  13.             if (sequence[i] == key)
  14.                 return true;
  15.         return false;
  16.     }
  17.  
  18.     public static boolean binarySearch(int[] sequence, int key) 
  19.     {
  20.         int low = 0, high = sequence.length - 1;
  21.         while (low <= high) 
  22.         {
  23.             int mid = (low + high) / 2;
  24.             if (key < sequence[mid])
  25.                 high = mid - 1;
  26.             else if (key > sequence[mid])
  27.                 low = mid + 1;
  28.             else
  29.                 return true;
  30.         }
  31.         return false;
  32.     }
  33.  
  34.     public static void QuickSort(int left, int right) 
  35.     {
  36.         if (right - left <= 0)
  37.             return;
  38.         else 
  39.         {
  40.             int pivot = sequence[right];
  41.             int partition = partitionIt(left, right, pivot);
  42.             QuickSort(left, partition - 1);
  43.             QuickSort(partition + 1, right);
  44.         }
  45.     }
  46.  
  47.     public static int partitionIt(int left, int right, long pivot) 
  48.     {
  49.         int leftPtr = left - 1;
  50.         int rightPtr = right;
  51.         while (true) 
  52.         {
  53.             while (sequence[++leftPtr] < pivot)
  54.                 ;
  55.             while (rightPtr > 0 && sequence[--rightPtr] > pivot)
  56.                 ;
  57.  
  58.             if (leftPtr >= rightPtr)
  59.                 break;
  60.             else
  61.                 swap(leftPtr, rightPtr);
  62.         }
  63.         swap(leftPtr, right);
  64.         return leftPtr;
  65.     }
  66.  
  67.     public static void swap(int dex1, int dex2) 
  68.     {
  69.         int temp = sequence[dex1];
  70.         sequence[dex1] = sequence[dex2];
  71.         sequence[dex2] = temp;
  72.     }
  73.  
  74.     public static void main(String args[]) 
  75.     {
  76.         Random random = new Random();
  77.  
  78.         for (int i = 0; i < N; i++)
  79.             sequence[i] = Math.abs(random.nextInt(100));
  80.  
  81.         Scanner sc = new Scanner(System.in);
  82.         System.out.println("Enter the key to be searched: ");
  83.         int k = sc.nextInt();
  84.  
  85.         System.out
  86.                 .println("Time taken to search key using sequential search: ");
  87.         long startTime = System.nanoTime();
  88.         boolean result = sequentialSearch(sequence, k);
  89.         long endTime = System.nanoTime();
  90.  
  91.         if (result == true)
  92.             System.out.println("Key found in " + (endTime - startTime)
  93.                     + " nanoseconds");
  94.         else
  95.             System.out.println("Key doesn't exist, execution time "
  96.                     + (endTime - startTime) + " nanoseconds");
  97.  
  98.         System.out.println("Time taken to search key using binary search: ");
  99.         QuickSort(0, N - 1);
  100.         startTime = System.nanoTime();
  101.         result = sequentialSearch(sequence, k);
  102.         endTime = System.nanoTime();
  103.  
  104.         if (result == true)
  105.             System.out.println("Key found in " + (endTime - startTime)
  106.                     + " nanoseconds");
  107.         else
  108.             System.out.println("Key doesn't exist, execution time "
  109.                     + (endTime - startTime) + " nanoseconds");
  110.         sc.close();
  111.     }
  112. }

Output:

advertisement
$ javac Sequential_Binary_Compare.java
$ java Sequential_Binary_Compare
 
Enter the key to be searched: (N=100)
85
Time taken to search key using sequential search: 
Key found in 14696 nanoseconds
Time taken to search key using binary search: 
Key found in 6680 nanoseconds
 
Enter the key to be searched: (N=1000)
562
Time taken to search key using sequential search: 
Key doesn't exist, execution time 44422 nanoseconds
Time taken to search key using binary search: 
Key doesn't exist, execution time 43420 nanoseconds

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.