Java Program to Compare Binary and Sequential Search

Code:

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:

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


More Java Programs: