Question

Write a program to show the difference between linear search and binary search. Show the input test data for your program and the output produced by your program which clearly show that binary search is faster than linear search

Answer 1

import java.util.*;

public class ArraySearch {

  public static boolean LinearSearch(int arr[], int x) {

    int n = arr.length;

    for (int i = 0; i < n; i++) {

      if (arr[i] == x) return true;

    }

    return false;

  }

  public static boolean binarySearch(int arr[], int x) {

    int l = 0, r = arr.length - 1;

    while (l <= r) {

      int m = l + (r - l) / 2;

      if (arr[m] == x) return true;

      if (arr[m] < x) l = m + 1; else r = m - 1;

    }

    return false;

  }

  public static int[] CreateArray(int n) {

    int Arr[] = new int[n];

    Random R = new Random();

    for (int i = 0; i < n; i++) {

      Arr[i] = R.nextInt() % 100000 + 1;

    }

    return Arr;

  }

  public static void main(String[] args) {

    double T1, T2, T;

    for (int n = 10; n <= 100000; n = n * 10) {

      int[] Arr = CreateArray(n);

      Random R = new Random();

      int number = R.nextInt() % 100000 + 1;

      T1 = System.nanoTime();

      boolean found = LinearSearch(Arr, number);

      T2 = System.nanoTime();

      T = T2 - T1;

      System.out.print(n + " Linear_Search : " + T + " nanosecond ");

      T1 = System.nanoTime();

      found = binarySearch(Arr, number);

      T2 = System.nanoTime();

      T = T2 - T1;

      System.out.println(" Binary_Search : " + T + " nanosecond");

    }

  }

}

//SAMPLE OUTPUT

******************************************************************************************
PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION
******************************************************************************************