Consider a binary search of the following list. Trace the binary search process
ID: 3589615 • Letter: C
Question
Consider a binary search of the following list. Trace the binary search process (for part a) indicating at each step what is the first (start) index, the last (end) index and middle index during the search process.
a) Search the list for the value 26. How many comparisons did your search have to perform to find the value?
b) Search the list for the value 6. How many comparisons?
3 7 812 1422 [0] [1] [2] [3] [4] [5] 26 30 32 39 List of values to be searched [6] [7] [8] [9] array indices, for referenceExplanation / Answer
/***************************BinarySearch.java**************************************/
/**
* The Class BinarySearch.
*/
public class BinarySearch {
/**
* Number of comparision.
*
* @param numbers the numbers
* @param num the num
* @return the int
*/
public static int numberOfComparision(int numbers[], int num) {
int low = 0;
int high = numbers.length - 1;
int count = 0;
while (low <= high) {
int mid = (low + high) / 2;
count++;
if (numbers[mid] == num) {
return count;
} else if (numbers[mid] > num) {
high = mid - 1;
} else if (numbers[mid] < num) {
low = mid + 1;
}
}
return count;
}
/**
* The main method.
*
* @param args the arguments
*/
public static void main(String[] args) {
int[] numbers = new int[] { 3, 7, 8, 12, 14, 22, 26, 30, 32, 39 };
int totalComparision26 = numberOfComparision(numbers, 26);
System.out.println("Total number of comparision for 26: " + totalComparision26);
int totalComparision6 = numberOfComparision(numbers, 6);
System.out.println("Total number of comparision for 6: " + totalComparision6);
}
}
/********************************output***********************************/
Total number of comparision for 26: 4
Total number of comparision for 6: 3
Thanks a lot. Please let me know if you have any doubt.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.