Question 35 - Iterative binarySearch of 1D int array (focus: purpose, speed, accuracy):
public static int binarySearch(int[] data, int target) {
int start = 0;
int end = data.length - 1;
// Continue the search as long as the start index is less than or equal to the end index
while (start <= end) {
// Calculate the midpoint of the current search range
int mid = (start + end) / 2;
// If the target is less than the value at the midpoint, adjust the end index
if (target < data[mid]) {
end = mid - 1;
}
// If the target is greater than the value at the midpoint, adjust the start index
else if (target > data[mid]) {
start = mid + 1;
}
// If the target is equal to the value at the midpoint, return the index
else {
return mid;
}
}
// If the target is not found, return -1
return -1;
}
If you were to plug in the provided values:
int[] values = {1, 2, 3, 4, 5, 8, 8, 8};
int target = 8;
// Calling the binarySearch method and storing the result in the 'result' variable
int result = binarySearch(values, target);
Here’s a breakdown of the process:
- Initially, the search range is set with
start = 0
andend = 7
(length of the array - 1). - In the first iteration, the midpoint
mid
is calculated as(0 + 7) / 2 = 3
. Since thetarget (8)
is greater thandata[3] (4)
, the search continues in the right half of the array, andstart
is updated to4
. - In the second iteration, the midpoint is calculated as
(4 + 7) / 2 = 5
. Here, thetarget (8)
is equal todata[5]
, so the method returns5
as the index where the target is found.
As a result, the value returned by the call binarySearch(values, target)
is 5
. This indicates that the target value 8
is found at index 5
in the given array values
.
Here’s an example to try:
Fill in the blanks in the following Java code to declare an array of characters and choose a target character for a binary search. Once the blanks are filled, run the code to perform the binary search and determine whether the target character is present in the array. If found, print the index; otherwise, print a message indicating that the target character was not found.
public class CharBinarySearchExample {
public static int charBinarySearch(char[] data, char target) {
int start = 0;
int end = data.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (target < data[mid]) {
end = mid - 1;
} else if (target > data[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
// Fill in the blank: Declare an array of characters (similar to the previous example)
char[] characters = ____;
// Fill in the blank: Choose a target character to search for in the array
char targetChar = ____;
int result = charBinarySearch(characters, targetChar);
if (result != -1) {
System.out.println("Target character '" + targetChar + "' found at index " + result);
} else {
System.out.println("Target character '" + targetChar + "' not found in the array.");
}
}
}
Your task is to fill in the blanks with appropriate values for the array of characters (characters
) and the target character (targetChar
). After filling in the blanks, you can run the code to see the results of the binary search.