Question

Enhanced Binary Search

Consider the binary search algorithm in Section 14.6. If no match is found, the search method returns -1. Modify the method so that if a is not found, the method returns -k - 1, where k is the position before which the element should be inserted. (This is the same behavior as Arrays.binarySearch.) Upload a file named BinarySearcher.java that has the same methods the binary search class in Section 14.6.

• Test Case 2
• Test Case 1

Console

4

Expected: 4

10

Expected: 10

-7

Expected: -7

-----------------------------------------------

Input Files

//package Sorting3;

public class Main
{
        public static void main(String [] args)
        {
                int [] a = {0, 2, 5, 12, 27, 42, 45, 51, 59, 62, 74};

                System.out.println(BinarySearcher.search(a, 27));
                System.out.println("Expected: 4");

                System.out.println(BinarySearcher.search(a, 74));
                System.out.println("Expected: 10");

                System.out.println(BinarySearcher.search(a, 43));
                System.out.println("Expected: -7");
        }
}

in java

Answer 1

SOURCE CODE:

*Please follow the comments to better understand the code.

**Please look at the Screenshot below and use this code to copy-paste.

***The code in the below screenshot is neatly indented for better understanding.

public class Main
{
public static void main(String [] args)
{
int [] a = {0, 2, 5, 12, 27, 42, 45, 51, 59, 62, 74};

System.out.println(BinarySearcher.search(a, 27));
System.out.println("Expected: 4");

System.out.println(BinarySearcher.search(a, 74));
System.out.println("Expected: 10");

System.out.println(BinarySearcher.search(a, 43));
System.out.println("Expected: -7");
}
}

class BinarySearcher
{
public static int search(int[] arr,int key)
{
int index =-1;
int low=0,high=arr.length;
boolean found=false;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] < key)
{
//right part
low = mid + 1;
}
else if (arr[mid] > key)
{
//left part
high = mid - 1;
}
else if (arr[mid] == key)
{
//Key found here
index = mid;
found=true;
break;
}
index=mid;
}
if(!found)
return -index-1;
else
return index;
}
}

==================================================

OUTPUT:

4
Expected: 4
10
Expected: 10
-7
Expected: -7
======================================================

18 class BinarySearcher 19- 20 21 public static int search(int] arr,int key) int index-1; int boolean found-false; while (low <high) 23 24 25 26- 27 28 29 30 31 32 low-e,high-arr.length; int mid -(lowhigh) 2 if (arr[mid] < key) //right part low mid1; else if (arr[mid] > key) 34- 35 36 37 38 39- 40 41 42 43 //left part high mid 1; else if (arr[mid]key //Key found here index mid; found-true break; index-mid; 45 46 47 48 49 50 51 52 53 if(found) return-index-1 else return index;

Output: 4 Expected: 4 10 Expected: 10 7 Expected: -7

I f there are any doubts, comment down here. Weareright here to help you. H appyLearning..!! Please HITaLIKEif youlike the answer, it really Boosts us..! Please HITaLIKEif youlike the answer, it really Boosts us..!!