nt binSearch(int arr[], int lo, int hi, int x) { int q = (low + high) / 2; if(ar

Question

nt binSearch(int arr[], int lo, int hi, int x)

{
int q = (low + high) / 2;
if(arr[q] <= x && arr[q + 1] > x){
return q + 1;
}
else if(arr[q] == x){
return binSearch(arr, q + 1, high, x);
}
else if(arr[q] > x){
return binSearch(arr, low, q - 1, x);
}
else if(arr[q] < x){
return binSearch(arr, q + 1, high, x);
}
}

1. Based on the above function, write an iterative algorithm (based on a while loop) that implements the specification.

2. Calculate (and explain your answer) the maximum number of iterations of the while loop, as a function of n.

3. Finally, convert your iterative program into a program with a tail-recursive function (which is called from the main function).

Explanation / Answer

import java.util.Scanner; class BinarySearch { public static void main(String args[]) { int c, lo, hi, q, n, search, arr[]; Scanner in = new Scanner(System.in); System.out.println("Enter number of elements"); n = in.nextInt(); arr = new int[n]; System.out.println("Enter " + n + " integers"); for (c = 0; c

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---