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:
Easy Ways to Write a Java InputStream to an OutputStream
Convert Hex to ASCII in Java
Java Program to Construct an Expression Tree for an Postfix Expression
XML-Based Injection in Spring
Immutable Objects in Java
ETL with Spring Cloud Data Flow
Java Program to Perform Arithmetic Operations on Numbers of Size
Debug a JavaMail Program
The HttpMediaTypeNotAcceptableException in Spring MVC
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Java Program to Implement Hash Tree
Java Program to Check if it is a Sparse Matrix
Generic Constructors in Java
Java Program to Find Number of Articulation points in a Graph
Java Program to Implement Doubly Linked List
Guide to Guava Multimap
Anonymous Classes in Java
Java Program to Represent Graph Using Incidence Matrix
Giới thiệu Java 8
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Java Program to Implement Rolling Hash
Quick Guide to @RestClientTest in Spring Boot
A Guide to EnumMap
Lớp TreeMap trong Java
Using the Map.Entry Java Class
Java Program to Generate Random Numbers Using Probability Distribution Function
Java Program to Implement Singly Linked List
Feign – Tạo ứng dụng Java RESTful Client
Java Program to Implement Min Hash
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Ép kiểu trong Java (Type casting)
Java Program to Perform Searching Using Self-Organizing Lists