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); } }