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.

//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:

Java Program to Implement Gabow Algorithm
Java Program to Implement Sorted Circularly Singly Linked List
Java Program to Generate Random Numbers Using Probability Distribution Function
Java Program to Construct K-D Tree for 2 Dimensional Data
Java – Try with Resources
Receive email using IMAP
Java Program to Generate Date Between Given Range
Java Program to Implement Hash Tables
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree
List Interface trong Java
Difference Between Wait and Sleep in Java
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Java Program to Implement Ternary Tree
Vòng lặp for, while, do-while trong Java
Hướng dẫn Java Design Pattern – Flyweight
Using JWT with Spring Security OAuth (legacy stack)
Java Program to Check Cycle in a Graph using Topological Sort
Form Validation with AngularJS and Spring MVC
JWT – Token-based Authentication trong Jersey 2.x
Java Program to Find Nearest Neighbor for Dynamic Data Set
Java Program to Implement Patricia Trie
Java Program to Compute Cross Product of Two Vectors
Một số từ khóa trong Java
Java Program to Implement String Matching Using Vectors
Spring @RequestParam Annotation
Spring Boot - Admin Client
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Java Program to Check Whether a Given Point is in a Given Polygon
Predicate trong Java 8
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Lấy ngày giờ hiện tại trong Java
Java Program to Implement Find all Forward Edges in a Graph