Question

20.14 Program BinarySearch

Objectives

• Examine a binary search algorithm
• Debug existing code

Instructions

For this lab you will code directly in ZyBooks. That means no uploading a file. If you wish, you can copy the template code into your IDE, work out a solution, and paste that into the code window.

The problem
The code does not work on certain data sets. Fix the sets but do not alter the binary search algorithm.

The obvious
Yes, this is a problem that can be solved with one additional statement. It is the last third of the semester and don't you want a break??

Program BinarySearch

/**
* Binary search to fix data sets issues
*/
import java.util.Scanner;

public class BinarySearch {
/** Use binary search to find the key in the list */
public static int binarySearch(int[] list, int key) {
int low = 0;
int high = list.length - 1;

while (high >= low) {
int mid = (low + high) / 2;
if (key < list[mid])
high = mid - 1;
else if (key == list[mid])
return mid;
else
low = mid + 1;
}

return -low - 1;
}
  
public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int set = in.nextInt();
int key = in.nextInt();

int[][] datasets = { {},
{1,2,3,5,8,13,21,34,55,89},
{-81, -72, -63, -54, -45, -36, -27, -18, -9, 0},
{21, 34, 72, -63, 8, 5, -13, -27, -18, 1, 0, 2}
};
  
System.out.println("Searching for key " + key +
" in data set " + set +
" returned " + binarySearch(datasets[set], key));

}
}

Run your program as often as you'd like, before submitting for grading. Below, type any needed input values in the first box, then click Run program and observe the program's output in the second box.

Answer 1

For binary search the input array must be sorted. Here a statement is added to sort the array.

If you need any corrections kindly comment.

Program

/**
* Binary search to fix data sets issues
*/
import java.util.Scanner;
import java.util.Arrays;
public class BinarySearch {
/** Use binary search to find the key in the list */
public static int binarySearch(int[] list, int key) {
int low = 0;
int high = list.length - 1;

while (high >= low) {
int mid = (low + high) / 2;
if (key < list[mid])
high = mid - 1;
else if (key == list[mid])
return mid;
else
low = mid + 1;
}

return -low - 1;
}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int set = in.nextInt();
int key = in.nextInt();

int[][] datasets = { {},
{1,2,3,5,8,13,21,34,55,89},
{-81, -72, -63, -54, -45, -36, -27, -18, -9, 0},
{21, 34, 72, -63, 8, 5, -13, -27, -18, 1, 0, 2}
};
Arrays.sort(datasets[set]);//Sort the set before calling binary search
System.out.println("Searching for key " + key +
" in data set " + set +
" returned " + binarySearch(datasets[set], key));

}
}

Output

user@user-Lenovo-V330-15IKB:~/JavaPrograms$ java BinarySearch
3
-27
Searching for key -27 in data set 3 returned 1