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:
Returning Image/Media Data with Spring MVC
OAuth 2.0 Resource Server With Spring Security 5
Injecting Prototype Beans into a Singleton Instance in Spring
Spring MVC Content Negotiation
Java Program to Check Whether a Given Point is in a Given Polygon
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Immutable Map Implementations in Java
Guide to Guava Multimap
ThreadPoolTaskExecutor corePoolSize vs. maxPoolSize
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Predicate trong Java 8
Mệnh đề if-else trong java
Hướng dẫn Java Design Pattern – Null Object
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Java Optional as Return Type
ClassNotFoundException vs NoClassDefFoundError
An Intro to Spring Cloud Contract
Spring Boot - Runners
Overflow and Underflow in Java
Java CyclicBarrier vs CountDownLatch
Lớp Collectors trong Java 8
Spring Boot - Tomcat Deployment
Java Program to Implement Sieve Of Atkin
Setting Up Swagger 2 with a Spring REST API
Truyền giá trị và tham chiếu trong java
Java Program to Repeatedly Search the Same Text (such as Bible by building a Data Structure)
Jackson Ignore Properties on Marshalling
Checking for Empty or Blank Strings in Java
Java Program to Implement the Alexander Bogomolny’s UnOrdered Permutation Algorithm for Elements Fro...
Deploy a Spring Boot WAR into a Tomcat Server
Hướng dẫn kết nối cơ sở dữ liệu với Java JDBC
Tạo ứng dụng Java RESTful Client với thư viện Retrofit