Write a program that a. Calls a method that takes two parameters, an integer and

Question

Write a program that

a. Calls a method that takes two parameters, an integer and an integer array. The call should perform binary search and should return the index of the integer in the array if found and should return -(insertionPoint+ 1) if the number is not found. Print out the index in the main method.

b. Calls a second method that performs binary search recursively. It should take 4 parameters: 3 integers and an array of integers. It should return the index of the element if found, if not then it should return -1.

Part A JAVA Code:

import java. util.*;
public class BinarySearch {
   public static void insertionSort( int arr[] ) {
       int n = arr.length;
       int i, j, temp;
       for (i = 1; i < n; i++) {
           j = i;
           temp = arr[i];
           while (j > 0 && temp < arr[j - 1]) {
               arr[j] = arr[j - 1];
               j = j - 1;
           }
           arr[j] = temp;
       }
    }
   public static int binarySearch(int x, int[] arr) {
      
       int first, last, middle;
       first = 1;
       last = arr.length - 1 ;
       boolean flag = true;
       middle = (first + last) / 2;
       for (int i = 1; i < arr.length; i++) {         
           while (first <= last && flag == true) {
               if (arr[middle] < x) {
                   first = middle + 1;
               } else if (arr[middle] == x) {
                   first = 1;
                   last = arr.length - 1;
                   break;
               } else {
                   last = middle - 1;
               }
               middle = (first + last) / 2;
           }
       }
       if (first > last) {
           System.out.println(x + " is not present in the list.");
           flag = false;
           return last + 2;
       } else {
           System.out.println(x + " found at location " + (middle + 1) + ".");
           return middle + 1;
       }
   }

     public static void main(String[] args) {
       Scanner scan = new Scanner( System.in );
       System.out.println("Insertion Sort Test");
      
       int n, i, x;
       System.out.print("Enter number of integer elements: ");
       n = scan.nextInt();
       int arr[] = new int[n];
       System.out.println("Enter "+ n +" integer elements: ");
       for (i = 0; i < n; i++)
           arr[i] = scan.nextInt();
       System.out.println("Elements before sorting: ");     
       for (i = 0; i < n; i++)
           System.out.print(arr[i]+" ");         
       System.out.println();
      
       insertionSort(arr);
       System.out.println("Elements after sorting: ");     
       for (i = 0; i < n; i++)
           System.out.print(arr[i]+" ");
       System.out.println();
       System.out.println("Enter the search element: ");
       x = scan.nextInt();
       int y = binarySearch(x,arr);
       System.out.println("Index of the search integer: " +y);
   }
}

Explanation / Answer

Java Code:

b) Add the below method to Class BinarySearch .

public static int recursiveBinarySearch(int x,int first,int last,int[] arr){
int middle=(first+last)/2;
if(first>last){
System.out.println(x + " is not present in the list.");
return first;
}else if(arr[middle]==x){
System.out.println(x + " found at location " + middle + ".");
return middle;
}else if(arr[middle]>x){
last=middle-1;
return recursiveBinarySearch(x,first,last,arr);
}else{
first=middle+1;
return recursiveBinarySearch(x,first,last,arr);
}
  
}

NOTE: 1) Call above method like   int y=recursiveBinarySearch(x,0,arr.length-1,arr);

2) index is considered from 0 to arr.length-1 unlike your method binarySearch().

if you want index from 1 to arr.length just increment variable first and middle by 1 before returning.

3) your method binarySearch() will not find the first element of array on searching. To fix this initiliaze

first=0 instead of first=1

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.