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.
//This the the java program to compare the sequential and binary search import java.util.Random; import java.util.Scanner; public class Sequential_Binary_Compare { public static int N = 1000; public static int[] sequence = new int[N]; public static boolean sequentialSearch(int[] sequence, int key) { for (int i = 0; i < sequence.length; i++) if (sequence[i] == key) return true; return false; } public static boolean binarySearch(int[] sequence, int key) { int low = 0, high = sequence.length - 1; while (low <= high) { int mid = (low + high) / 2; if (key < sequence[mid]) high = mid - 1; else if (key > sequence[mid]) low = mid + 1; else return true; } return false; } public static void QuickSort(int left, int right) { if (right - left <= 0) return; else { int pivot = sequence[right]; int partition = partitionIt(left, right, pivot); QuickSort(left, partition - 1); QuickSort(partition + 1, right); } } public static int partitionIt(int left, int right, long pivot) { int leftPtr = left - 1; int rightPtr = right; while (true) { while (sequence[++leftPtr] < pivot) ; while (rightPtr > 0 && sequence[--rightPtr] > pivot) ; if (leftPtr >= rightPtr) break; else swap(leftPtr, rightPtr); } swap(leftPtr, right); return leftPtr; } public static void swap(int dex1, int dex2) { int temp = sequence[dex1]; sequence[dex1] = sequence[dex2]; sequence[dex2] = temp; } public static void main(String args[]) { Random random = new Random(); for (int i = 0; i < N; i++) sequence[i] = Math.abs(random.nextInt(100)); Scanner sc = new Scanner(System.in); System.out.println("Enter the key to be searched: "); int k = sc.nextInt(); System.out .println("Time taken to search key using sequential search: "); long startTime = System.nanoTime(); boolean result = sequentialSearch(sequence, k); long endTime = System.nanoTime(); if (result == true) System.out.println("Key found in " + (endTime - startTime) + " nanoseconds"); else System.out.println("Key doesn't exist, execution time " + (endTime - startTime) + " nanoseconds"); System.out.println("Time taken to search key using binary search: "); QuickSort(0, N - 1); startTime = System.nanoTime(); result = sequentialSearch(sequence, k); endTime = System.nanoTime(); if (result == true) System.out.println("Key found in " + (endTime - startTime) + " nanoseconds"); else System.out.println("Key doesn't exist, execution time " + (endTime - startTime) + " nanoseconds"); sc.close(); } }
Output:
$ 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
Related posts:
Count Occurrences of a Char in a String
Instance Profile Credentials using Spring Cloud
Java Program to Solve Tower of Hanoi Problem using Stacks
Java Program to Find Second Smallest of n Elements with Given Complexity Constraint
Jackson Ignore Properties on Marshalling
Returning Image/Media Data with Spring MVC
Java Program to Implement Sparse Matrix
Inject Parameters into JUnit Jupiter Unit Tests
Spring Boot - Creating Docker Image
Java Program to Implement Stack
Java Program to Implement Bloom Filter
Java Program to Implement Fenwick Tree
How to Read HTTP Headers in Spring REST Controllers
Apache Commons Collections MapUtils
Cài đặt và sử dụng Swagger UI
Spring Boot - Internationalization
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Java Program to Implement ArrayList API
Spring Security OAuth2 – Simple Token Revocation
Setting Up Swagger 2 with a Spring REST API
Java NIO2 Path API
Lập trình hướng đối tượng (OOPs) trong java
Java Program to Check whether Graph is Biconnected
Java Program to Check Whether an Input Binary Tree is the Sub Tree of the Binary Tree
The Dining Philosophers Problem in Java
An Introduction to ThreadLocal in Java
Java Program to Implement ConcurrentLinkedQueue API
Java Program to Find the GCD and LCM of two Numbers
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Check if there is mail waiting
Java Program to Implement Cubic convergence 1/pi Algorithm
Easy Ways to Write a Java InputStream to an OutputStream