Question

I already have the code of this program, I just want to know how to fix the code to Implement the 5th function

（System.nanotime() and System.currentTimeMillis() methods）

What Code does:

Introduction

Searching is a fundamental operation of computer applications and can be performed using either the inefficient linear search algorithm with a time complexity of O (n) or by using the more efficient binary search algorithm with a time complexity of O (log n).

Task Requirements

In this lab, you will write a Java program to search for an integer in an array using recursive and non-recursive binary search.

Classes:

1. Binarysearch class

Instance variables

1. Private data members and Scanner object.
2. You may choose to include here all instance variables shared by both recursive and non-recursive methods. These may include shared array index and search key variables.

Methods

1. nonRecursiveBinarySearch (uses iterative/looping construct)

Receives an array of integers and the search key – number to search. If the number is present in the array the method returns its index location and prints the message: ‘number ___ found at index ___’ on the screen. If the number is not found in the array the method returns a sentinel value of -1 and prints the message ‘number _ was not found’.

2. recursiveBinarySearch (uses recursion)

A method that receives an array of randomly generated integers, the first index and last index of the array, and the number to search. The method then recursively searches for the number entered by the user on the keyboard. Returns the index position if the number is present in the array and prints the message ‘number ___ found at index ___’ on the screen. Returns a sentinel value of -1 if the number is not found and prints the message ‘number __ was not found’.

3. generateRandomInts

Uses the more SecureRandom class to generate random integers between 10 and 100. Returns an array of random numbers: randomArr, that is, an array that will be populated with 20 randomly generated integer values mainly in the range of 10 to 100 – boundary values excluded i.e. 10

This method prints the sorted array of random integers on the screen.

4. remainingElements

This method displays elements remaining each time a half of the array is dropped.

5. System.nanotime() and System.currentTimeMillis() methods

Use these two methods of the System class to determine how long the recursive and non-recursive binary Search operations in (a) and (b) take in nanoseconds and milliseconds. Time taken by each operation should be displayed on the screen. Hint: wrap each method in (a) and (b) with the timing methods.

6. You may create one more additional method.

2. Lab3binsearchTest class

Creates a menu as follows:

Select your option in the menu:

1. Initialize and populate an array of 20 random integers.
2. Perform a recursive binary search.
3. Perform a non-recursive binary search.
4. Exit.

code:

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

class BinarySearch{
        
        // Non recursive binary search
        public int nonRecursiveBinarySearch(int arr[],int target)
        {
                int low=0,high=arr.length-1;
                while(low<=high)
                {
                        remainingElements(arr,low,high);
                        int mid=(low+high)/2;
                        if(arr[mid]==target)
                        {
                                System.out.println("Number "+target +" is found at index "+mid+" :Non recursive binary search");
                                return mid;
                        }
                        else if(arr[mid]<target)
                                low=mid+1;
                        else
                                high=mid-1;
                }
                System.out.println("Number "+target+" was not found   :Non recursive binary search");
                return -1;
        }
        
        // recursive binarySearch
        public int recursiveBinarySearch(int arr[],int first,int last,int target)
        {
                if(first<=last)
                {
                        remainingElements(arr,first,last);
                        int mid=(first+last)/2;
                        if(arr[mid]==target)
                        {
                                System.out.println("Number "+target +" is found at index "+mid+"  : recursive binary search");
                                return mid;
                        }
                        else if(arr[mid]<target)
                                return recursiveBinarySearch(arr,mid+1,last,target);
                        else
                                return recursiveBinarySearch(arr,first,mid-1,target);
                }
                // if not found
                System.out.println("Number "+target +" is not found : recursive binary search");
                return -1;
                
        }
        
        // display method will the array content between two index
        public void remainingElements(int arr[],int l,int r)
        {
                for(int i=l;i<=r;i++)
                        System.out.print(arr[i]+" ");
                System.out.println();
        }
        
        int[] generateRandomInts()
        {
                int arr[]=new int[20];
                Random rand=new Random();
                for(int i=0;i<20;i++)
                        arr[i]=rand.nextInt(89)+11; // generate between 11 to 99
                // sort the array
                Arrays.sort(arr);
                return arr;
        }
        
        public void calculateTime(int arr[],int target)
        {
                // for recusive 
                long start=System.nanoTime();
                recursiveBinarySearch(arr,0,arr.length-1,target);
                long time=System.nanoTime()-start;
                System.out.println("Recursive method will take "+time+"ns");
                
            start=System.currentTimeMillis();
                recursiveBinarySearch(arr,0,arr.length-1,target);
                time=System.currentTimeMillis()-start;
                System.out.println("Recursive method will take "+time+"ms");
                
                
                // for non  recusive 
                          start=System.nanoTime();
                                nonRecursiveBinarySearch(arr,target);
                                 time=System.nanoTime()-start;
                                System.out.println("Non Recursive method will take "+time+"ns");
                                
                            start=System.currentTimeMillis();
                                nonRecursiveBinarySearch(arr,target);
                                time=System.currentTimeMillis()-start;
                                System.out.println("Non Recursive method will take "+time+"ms");
                                
                                
                
        }
        
        
        
}


public class Lab3binarysearchTest {
        

        public static void main(String[] args) {
                
       Scanner sc=new Scanner(System.in);
       BinarySearch bs=new BinarySearch();
       int arr[] = null;
       while(true)
       {
           System.out.println("Select your option int the menu below:\n"
                        + "1.Initialize and populate an array of 20 random integers\n"
                        + "2.Perform a recursive binary search\n"
                        + "3.Perfrom a non-recursive binary search\n"
                        + "4.Exit");
           int choice=sc.nextInt();
           if(choice==1)
           {
                   arr=bs.generateRandomInts();
                   System.out.println("Array of randomly generated integers:");
                   bs.remainingElements(arr, 0, arr.length-1);
                   
           }
           else if(choice==2)
           {
                   System.out.print("Please enter an integer value to search: ");
                int target=sc.nextInt();
                bs.recursiveBinarySearch(arr, 0, arr.length-1, target);
           }
           else if(choice==3)
           {
                   System.out.print("Please enter an integer value to search: ");
               int target=sc.nextInt();
               bs.nonRecursiveBinarySearch(arr, target);
           }
           else if(choice==4)
                   System.exit(0);
           else
                   System.out.println("Enter a valid choice");
           
       }
                
        }

}

Answer 1

If I have understood your problem/doubt correctly, you want to know when and where to call the 5th method and also how to not print the results twice.

I have answered below according to that assumption. If this is not what you want please comment so that I can understand your doubt more properly and try to solve it

You can change the calculateTime function as shown below which is almost same as your code but added a boolean variable 'recursive' to check time for recursive or non-recursive approach. And also, instead of running the same method (either recursive or non-recursive) twice for checking in both nano and milli seconds, we can call the method once and check both times for the exact same function call.

public void calculateTime(int arr[],int target, boolean recusive)
        {
            long startNano, startMilli, timeNano, timeMilli;
            if(!recusive)   // for recusive 
            {
                startNano=System.nanoTime();
                startMilli=System.currentTimeMillis();
                
                recursiveBinarySearch(arr,0, arr.length-1, target);
                
                timeNano=System.nanoTime()-startNano;
                timeMilli=System.currentTimeMillis()-startMilli;
                System.out.println("Recursive method will take "+timeNano+"ns");
                System.out.println("Recursive method will take "+timeMilli+"ms");
                
            }
            else if(recusive)       // for non  recusive 
            {
                startNano=System.nanoTime();
                startMilli=System.currentTimeMillis();
                
                nonRecursiveBinarySearch(arr,target);
                
                timeNano=System.nanoTime()-startNano;
                timeMilli=System.currentTimeMillis()-startMilli;
                System.out.println("Non Recursive method will take "+timeNano+"ns");
                System.out.println("Non Recursive method will take "+timeMilli+"ms");
            }
                
        }

I have also changed the code in main function. The changes are shown below

else if(choice==2)
{
    System.out.print("Please enter an integer value to search: ");
    int target=sc.nextInt();
    bs.calculateTime(arr, target, false);
}
else if(choice==3)
{
   System.out.print("Please enter an integer value to search: ");
   int target=sc.nextInt();
   bs.calculateTime(arr, target, true);
}

Instead of directly calling the recursive and non-recursive methods, we can call the 'calculateTime' method which inturn calls the required methods and notes the time