***Is this code correct? I am trying to do binary Search on an array of 20 strin
ID: 3691812 • Letter: #
Question
***Is this code correct? I am trying to do binary Search on an array of 20 strings. The variable comparisons is just to get the number of iterations (part of the assigment).
***How the recursive version of this looks like?
// Binary Search method
public static boolean binarySearch(String[] a, String item){
int start = 0;
int end = a.length - 1;
int pos = -1;
boolean found = false;
int comparisons = 0 ;
while (!found && start != end) {
comparisons++;
int middle = (end - start) / 2;
if (a[middle].compareTo(item) <0 ) {
end = middle - 1;
} else if (a[middle].compareTo(item) > 0) {
start = middle + 1;
} else {
found = true;
pos = middle;
}
}
System.out.println(comparisons);
return found;
Explanation / Answer
The above program that you wrote is absolutely correct, but binary search works on a sorted array
above program work's on alphabetically sorted array.
recursive version of the above program looks like below.
------------------------------------------------------------------------------------
public static int recursiveBinarySearch(string[] a, int start, int end, int item) {
if (start < end) {
int mid = start + (end - start) / 2;
if (a[middle].compareTo(item) <0) {
return recursiveBinarySearch(a, start, mid, item);
} else if (a[middle].compareTo(item) >0) {
return recursiveBinarySearch(a, mid+1, end , item);
} else {
return mid;
}
}
return -(start + 1);
}
//calling the method.
recursiveBinarySearch(sortedArray,0,arr1.length,item);
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.