Question

1. Write a method in JAVA, called binarySearch, that returns the index of the key element if found in the array, otherwise it will return the value of minus(insertion point +1).
2. In main, use an initializer list create an array of ints called nums holding the following values: 1, 4, 13, 43, -25, 17, 22, -37, 29. Test your binarySearch method on nums with a key value number in it (e.g. 4) and one that is not (e.g. 100).
3. Ex. Given the array values {1, 4, 4, 22, -5, 10, 21, -47, 23}, the array will be sorted as -47, -5, 1, 4, 4, 10, 21, 22, 23. The index for the key value of 4 will be 3. The return value when searching for 6 will be the insertion point for 6 which is index of 5, so the return will be minus(5+1) = -6.
4. Create an int array of size 20, called data and write a method to fill the array with random ints [-100, 100]. Recall that random’s nextInt( x) method returns a value from 0 to x-1. The upper bound is exclusive. Modify the values to fit the required ranges.
5. Use the binarySearch method you previously wrote to return the index of the key value searched for in data for the client to print. Let’s use 10 as the key value for every run. Notice that 10 may not be part of the data array every run.
6. Print the value of the key value searched for (10) and the index of the value, which is the value of -(insertion point +1).

Answer 1

//Java program

import java.util.Random;

public class BinarySearch {
   public static void bubbleSort(int a[],int n){
       for(int i=n-1;i>=0;i--){
           for(int j=0;j<i;j++){
               if(a[j]>a[j+1]){
                   int temp=a[j];
                   a[j]=a[j+1];
                   a[j+1]=temp;
               }
           }
       }
   }
   public static int binarySearch(int a[], int key, int low, int high)
   {
   if (high <= low)
   return ((key > a[low])? (low + 1): low) +1;
   int mid = (low + high)/2;
   if(key == a[mid]) return mid;
  
   if(key > a[mid]) return binarySearch(a, key, mid+1, high);
  
   return binarySearch(a, key, low, mid-1);
   }
  
   public static void main(String args[]) {
       int arr[] = {1, 4, 13, 43, -25, 17, 22, -37, 29};
       bubbleSort(arr,arr.length);
       System.out.println("Index of 4 : "+binarySearch(arr,4,0,arr.length-1));
       System.out.println("Index of 100 : "+binarySearch(arr,100,0,arr.length-1));
      
       int arr1[] = {1, 4, 4, 22, -5, 10, 21, -47, 23};
       bubbleSort(arr1,arr1.length);
       System.out.println("\n\nIndex of 4 : "+binarySearch(arr1,4,0,arr1.length-1));
       System.out.println("Index of 100 : "+binarySearch(arr1,6,0,arr1.length-1));
      
       int arr2[] = new int[20];
       Random random = new Random();
       for(int i=0;i<20;i++) {
           arr2[i] = -100+random.nextInt(200);
       }
       bubbleSort(arr2,arr2.length);
       System.out.println("\n\nIndex of 10 : "+binarySearch(arr2,4,0,arr2.length-1));
      
   }
}
//sample output