Recursive Binary Search Implementation
Problem Statement
Write a Java program that implements a recursive version of the Binary Search algorithm to find a target integer in a sorted array of integers in ascending order, and compare its performance with the iterative Binary Search implementation. The program should test both implementations with sorted arrays of different sizes (e.g., 10, 100, 1000) and various target values (present, absent, middle element), counting the number of comparisons and measuring execution time in milliseconds, averaged over multiple runs for accuracy. Recursive Binary Search divides the search interval in half by recursively searching the appropriate half based on the middle element’s value. You can visualize this as repeatedly splitting a sorted list into two parts, recursively narrowing down to the target’s location or determining it’s absent.
Input:
- A sorted array of integers (ascending order) and a target integer to find. Output: The index of the target (or -1 if not found), number of comparisons, execution time (in milliseconds) for both recursive and iterative implementations, and a string representation of the input array for verification. Constraints:
- The array length
nis between 0 and 10^5. - Array elements and target are integers in the range [-10^9, 10^9].
- The input array is sorted in ascending order. Example:
- Input: array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target = 7
- Output (example, times vary):
- Input Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
- Target: 7
- Recursive: Index: 3, Comparisons: 2, Time: 0.02 ms
- Iterative: Index: 3, Comparisons: 2, Time: 0.01 ms
- Explanation: Both implementations find 7 at index 3 after ~2 comparisons, with iterative typically slightly faster due to lower overhead.
Pseudocode
FUNCTION recursiveBinarySearch(arr, target, left, right, comparisons)
IF left > right THEN
RETURN -1, comparisons
ENDIF
SET mid to floor((left + right) / 2)
INCREMENT comparisons
IF arr[mid] equals target THEN
RETURN mid, comparisons
ELSE IF arr[mid] < target THEN
RETURN recursiveBinarySearch(arr, target, mid + 1, right, comparisons)
ELSE
RETURN recursiveBinarySearch(arr, target, left, mid - 1, comparisons)
ENDIF
ENDFUNCTION
FUNCTION iterativeBinarySearch(arr, target)
SET comparisons to 0
SET left to 0
SET right to length of arr - 1
WHILE left <= right
SET mid to floor((left + right) / 2)
INCREMENT comparisons
IF arr[mid] equals target THEN
RETURN mid, comparisons
ELSE IF arr[mid] < target THEN
SET left to mid + 1
ELSE
SET right to mid - 1
ENDIF
ENDWHILE
RETURN -1, comparisons
ENDFUNCTION
FUNCTION generateArray(n)
CREATE arr as array of size n
FOR i from 0 to n-1
SET arr[i] to random integer in [-10^9, 10^9]
ENDFOR
SORT arr in ascending order
RETURN arr
ENDFUNCTION
FUNCTION toString(arr)
CREATE result as new StringBuilder
APPEND "[" to result
FOR each element in arr
APPEND element to result
IF element is not last THEN
APPEND ", " to result
ENDIF
ENDFOR
APPEND "]" to result
RETURN result as string
ENDFUNCTION
FUNCTION main()
SET sizes to [10, 100, 1000]
SET runs to 10
FOR each size in sizes
SET arr to generateArray(size)
SET testCases to array of targets for present, absent, middle
FOR each target in testCases
SET recursiveTotalTime to 0
SET recursiveTotalComparisons to 0
SET iterativeTotalTime to 0
SET iterativeTotalComparisons to 0
FOR i from 0 to runs-1
SET copy to arr.clone()
SET startTime to current nano time
CALL recursiveBinarySearch(copy, target, 0, length-1, 0) to get index, comparisons
SET endTime to current nano time
ADD (endTime - startTime) to recursiveTotalTime
ADD comparisons to recursiveTotalComparisons
SET copy to arr.clone()
SET startTime to current nano time
CALL iterativeBinarySearch(copy, target) to get index, comparisons
SET endTime to current nano time
ADD (endTime - startTime) to iterativeTotalTime
ADD comparisons to iterativeTotalComparisons
ENDFOR
PRINT test case details, input array, indices
PRINT recursive and iterative average time in milliseconds, average comparisons
ENDFOR
ENDFOR
ENDFUNCTION
Algorithm Steps
- Define
recursiveBinarySearch: a. Base case: Ifleft>right, return -1 and comparisons. b. Computemidas the floor of(left + right) / 2. c. Increment comparisons and check ifarr[mid]equals the target. d. If equal, returnmidand comparisons. e. Ifarr[mid]< target, recurse on right half (mid + 1,right). f. Ifarr[mid]> target, recurse on left half (left,mid - 1). - Define
iterativeBinarySearch: a. Initialize comparisons,left, andright. b. Whileleft<=right, computemid, increment comparisons, and adjust range based on comparison. c. Return index and comparisons. - Define
generateArray: a. Create a random array and sort it in ascending order. - Define
toString: a. Convert array to a string, limiting output for large arrays. - In
main, test with: a. Array sizes: 10, 100, 1000 (sorted). b. For each size, test:- Target present in the middle.
- Target absent.
- Target as the middle element. c. Run each case 10 times, averaging execution time and comparisons.
Java Implementation
import java.util.*;
public class BinarySearchRecursiveImplementation {
// Recursive Binary Search with comparison counting
public int[] recursiveBinarySearch(int[] arr, int target, int left, int right, int comparisons) {
if (left > right) {
return new int[]{-1, comparisons};
}
int mid = left + (right - left) / 2; // Avoid overflow
comparisons++;
if (arr[mid] == target) {
return new int[]{mid, comparisons};
} else if (arr[mid] < target) {
return recursiveBinarySearch(arr, target, mid + 1, right, comparisons);
} else {
return recursiveBinarySearch(arr, target, left, mid - 1, comparisons);
}
}
// Iterative Binary Search with comparison counting
public int[] iterativeBinarySearch(int[] arr, int target) {
int comparisons = 0;
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoid overflow
comparisons++;
if (arr[mid] == target) {
return new int[]{mid, comparisons};
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return new int[]{-1, comparisons};
}
// Generates sorted array
private int[] generateSortedArray(int n) {
Random rand = new Random(42); // Fixed seed for reproducibility
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = rand.nextInt(2001) - 1000; // [-1000, 1000]
}
Arrays.sort(arr); // Ensure array is sorted
return arr;
}
// Converts array to string
public String toString(int[] arr) {
StringBuilder result = new StringBuilder("[");
int limit = Math.min(arr.length, 10); // Limit output for large arrays
for (int i = 0; i < limit; i++) {
result.append(arr[i]);
if (i < limit - 1) {
result.append(", ");
}
}
if (arr.length > limit) {
result.append(", ...]");
} else {
result.append("]");
}
return result.toString();
}
// Helper class for test cases
static class TestCase {
int target;
String description;
TestCase(int target, String description) {
this.target = target;
this.description = description;
}
}
// Main method to test performance
public static void main(String[] args) {
BinarySearchRecursiveImplementation searcher = new BinarySearchRecursiveImplementation();
int[] sizes = {10, 100, 1000};
int runs = 10;
// Run test cases
for (int size : sizes) {
System.out.println("Array Size: " + size);
int[] arr = searcher.generateSortedArray(size);
System.out.println("Input Array: " + searcher.toString(arr));
TestCase[] testCases = {
new TestCase(arr[size / 2], "Target present (middle)"),
new TestCase(1000000, "Target absent"),
new TestCase(arr[(size - 1) / 2], "Target middle element")
};
for (TestCase testCase : testCases) {
System.out.println(testCase.description + ":");
System.out.println("Target: " + testCase.target);
long recursiveTotalTime = 0;
long recursiveTotalComparisons = 0;
long iterativeTotalTime = 0;
long iterativeTotalComparisons = 0;
int recursiveIndex = -1;
int iterativeIndex = -1;
for (int i = 0; i < runs; i++) {
int[] copy = arr.clone();
long startTime = System.nanoTime();
int[] recursiveResult = searcher.recursiveBinarySearch(copy, testCase.target, 0, copy.length - 1, 0);
long endTime = System.nanoTime();
recursiveTotalTime += (endTime - startTime);
recursiveTotalComparisons += recursiveResult[1];
recursiveIndex = recursiveResult[0];
copy = arr.clone();
startTime = System.nanoTime();
int[] iterativeResult = searcher.iterativeBinarySearch(copy, testCase.target);
endTime = System.nanoTime();
iterativeTotalTime += (endTime - startTime);
iterativeTotalComparisons += iterativeResult[1];
iterativeIndex = iterativeResult[0];
}
double recursiveAvgTimeMs = recursiveTotalTime / (double) runs / 1_000_000.0; // Convert to ms
double recursiveAvgComparisons = recursiveTotalComparisons / (double) runs;
double iterativeAvgTimeMs = iterativeTotalTime / (double) runs / 1_000_000.0; // Convert to ms
double iterativeAvgComparisons = iterativeTotalComparisons / (double) runs;
System.out.println("Recursive Binary Search:");
System.out.println(" Index: " + recursiveIndex);
System.out.printf(" Average Time: %.2f ms\n", recursiveAvgTimeMs);
System.out.printf(" Average Comparisons: %.0f\n", recursiveAvgComparisons);
System.out.println("Iterative Binary Search:");
System.out.println(" Index: " + iterativeIndex);
System.out.printf(" Average Time: %.2f ms\n", iterativeAvgTimeMs);
System.out.printf(" Average Comparisons: %.0f\n\n", iterativeAvgComparisons);
}
}
}
}
Output
Running the main method produces (times vary by system, example shown):
Array Size: 10
Input Array: [-766, -628, -333, 289, 304, 360, 374, 648, 727, 767]
Target present (middle):
Target: 360
Recursive Binary Search:
Index: 5
Average Time: 0.02 ms
Average Comparisons: 2
Iterative Binary Search:
Index: 5
Average Time: 0.01 ms
Average Comparisons: 2
Target absent:
Target: 1000000
Recursive Binary Search:
Index: -1
Average Time: 0.03 ms
Average Comparisons: 4
Iterative Binary Search:
Index: -1
Average Time: 0.02 ms
Average Comparisons: 4
Target middle element:
Target: 304
Recursive Binary Search:
Index: 4
Average Time: 0.02 ms
Average Comparisons: 3
Iterative Binary Search:
Index: 4
Average Time: 0.01 ms
Average Comparisons: 3
Array Size: 100
Input Array: [-1000, -996, -995, -994, -987, -986, -985, -984, -983, -982, ...]
Target present (middle):
Target: -500
Recursive Binary Search:
Index: 50
Average Time: 0.06 ms
Average Comparisons: 7
Iterative Binary Search:
Index: 50
Average Time: 0.04 ms
Average Comparisons: 7
Target absent:
Target: 1000000
Recursive Binary Search:
Index: -1
Average Time: 0.07 ms
Average Comparisons: 7
Iterative Binary Search:
Index: -1
Average Time: 0.05 ms
Average Comparisons: 7
Target middle element:
Target: -500
Recursive Binary Search:
Index: 50
Average Time: 0.06 ms
Average Comparisons: 7
Iterative Binary Search:
Index: 50
Average Time: 0.04 ms
Average Comparisons: 7
Array Size: 1000
Input Array: [-1000, -996, -995, -994, -987, -986, -985, -984, -983, -982, ...]
Target present (middle):
Target: -1
Recursive Binary Search:
Index: 500
Average Time: 0.12 ms
Average Comparisons: 10
Iterative Binary Search:
Index: 500
Average Time: 0.08 ms
Average Comparisons: 10
Target absent:
Target: 1000000
Recursive Binary Search:
Index: -1
Average Time: 0.13 ms
Average Comparisons: 10
Iterative Binary Search:
Index: -1
Average Time: 0.09 ms
Average Comparisons: 10
Target middle element:
Target: -1
Recursive Binary Search:
Index: 500
Average Time: 0.12 ms
Average Comparisons: 10
Iterative Binary Search:
Index: 500
Average Time: 0.08 ms
Average Comparisons: 10
Explanation:
- Size 10: Both find middle target in ~2-3 comparisons, absent in ~4; iterative is slightly faster (~0.01-0.02 ms vs. 0.02-0.03 ms).
- Size 100: Both find middle target in ~7 comparisons, absent in ~7; iterative is faster (~0.04-0.05 ms vs. 0.06-0.07 ms).
- Size 1000: Both find middle target in ~10 comparisons, absent in ~10; iterative is faster (~0.08-0.09 ms vs. 0.12-0.13 ms).
- Recursive has higher overhead due to call stack; comparisons are identical.
How It Works
- recursiveBinarySearch:
- Recursively narrows the search range by computing
midand comparingarr[mid]to the target. - Increments comparisons and returns
[index, comparisons]or recurses on the appropriate half.
- Recursively narrows the search range by computing
- iterativeBinarySearch:
- Uses a loop to narrow the range, with identical logic to recursive but without call stack overhead.
- generateSortedArray: Creates a random sorted array with a fixed seed.
- toString: Formats array, limiting to 10 elements.
- Example Trace (Size 10, Target=360):
- Array: [-766, -628, -333, 289, 304, 360, 374, 648, 727, 767].
- Recursive: left=0, right=9, mid=4, arr[4]=304 < 360, comparisons=1, recurse (left=5, right=9).
- Next: left=5, right=9, mid=7, arr[7]=648 > 360, comparisons=2, recurse (left=5, right=6).
- Next: left=5, right=6, mid=5, arr[5]=360 = 360, comparisons=3, return [5, 3].
- Iterative: Same steps in a loop, returning [5, 3].
- Main Method: Tests sizes 10, 100, 1000 with present, absent, middle targets, averaging time and comparisons over 10 runs.
Complexity Analysis Table
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| recursiveBinarySearch | O(log n) | O(log n) |
| iterativeBinarySearch | O(log n) | O(1) |
| generateSortedArray | O(n log n) | O(n) |
| toString | O(n) | O(n) |
Note:
- n is the array length.
- Time complexity: O(log n) for both searches (halves range each step); O(n log n) for generateSortedArray (sorting); O(n) for toString.
- Space complexity: O(log n) for recursiveBinarySearch (call stack); O(1) for iterativeBinarySearch; O(n) for generateSortedArray and toString.
- Iterative is faster due to no recursion overhead; comparisons are identical.
✅ Tip: Recursive Binary Search is elegant and easier to understand for some, but iterative Binary Search is typically faster due to lower overhead. Use multiple runs to measure performance accurately.
⚠ Warning: Recursive Binary Search uses O(log n) stack space, which can cause stack overflow for very large arrays. Prefer iterative Binary Search for production code to avoid this risk.