Recursive Binary Search The binary search algorithm from Chapter 9 is a very eff
ID: 3568725 • Letter: R
Question
Recursive Binary Search
The binary search algorithm from Chapter 9 is a very efficient algorithm for searching an ordered list. The
algorithm (in pseudocode) is as follows:
highIndex - the maximum index of the part of the list being searched
lowIndex - the minimum index of the part of the list being searched
target -- the item being searched for
//look in the middle
middleIndex = (highIndex + lowIndex) / 2
if the list element at the middleIndex is the target
return the middleIndex
else
if the list element in the middle is greater than the target
search the first half of the list
else
search the second half of the list
Notice the recursive nature of the algorithm. It is easily implemented recursively. Note that three parameters are
needed
Explanation / Answer
package com.java2novice.algos;
public class MyRecursiveBinarySearch {
public static int recursiveBinarySearch(int[] sortedArray, int start, int end, int key) {
if (start < end) {
int mid = start + (end - start) / 2;
if (key < sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, start, mid, key);
} else if (key > sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, mid+1, end , key);
} else {
return mid;
}
}
return -(start + 1);
}
public static void main(String[] args) {
int[] arr1 = {2,45,234,567,876,900,976,999};
int index = recursiveBinarySearch(arr1,0,arr1.length,45);
System.out.println("Found 45 at "+index+" index");
index = recursiveBinarySearch(arr1,0,arr1.length,999);
System.out.println("Found 999 at "+index+" index");
index = recursiveBinarySearch(arr1,0,arr1.length,876);
System.out.println("Found 876 at "+index+" index");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.