Answer:
import java.util.*;
public class Main
{
int binarySearch1(int arr[], int l, int r, int x) //Binary search using recursion
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) .// if the mid element is the search elemnent return mid;
return mid;
if (arr[mid] > x)
return binarySearch1(arr, l, mid - 1, x); //if x is on the right side search on right side.
return binarySearch1(arr, mid + 1, r, x); // if x is on left side search on left side.
}
return -1;
}
int binarySearch2(int arr[], int x) //Binary search using Iteration
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) // if the mid element is the search elemnent return mid;
return mid;
if (arr[mid] < x) // if x is on left side search on left side.
l = mid + 1;
else
r = mid - 1; //if x is on the right side search on right side.
}
return -1;
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
System.out.println("Enter the elemnts of the array"); //taking elemnts of array
int n=scan.nextInt();
int arr[]= new int[n];
for(int i=0;i<n;i++)
arr[i]=scan.nextInt();
System.out.println("Enter the number you want to search");
int k=scan.nextInt();
Main ob = new Main();
long start1 = System.nanoTime(); //systems current time in nano seconds
int p=ob.binarySearch1(arr,0,n-1,k);
long end1 = System.nanoTime(); //systems current time in nano seconds
long microseconds1 = (end1 - start1) / 1000; //measuring time elapsed for recusive binary search
//long startTime2 = System.currentTimeMillis();
long start2 = System.nanoTime(); //systems current time in nano seconds
int q= ob.binarySearch2(arr,k);
long end2 = System.nanoTime(); //systems current time in nano seconds
long microseconds2 = (end2 - start2) / 1000; //measuring the time elapsed for iterative binary search
System.out.println(microseconds1); //Printing the time elapsed for both the methods
System.out.println(microseconds2);
}
}
Explanation- Since in recursive binary search there will always be a overhead of manipulating call stack the time taken by recursive binary search is a little more than iterative binary search. Though the time complexity of both the algorithm is O(nLogn).
Explanation:
