/***********************************************************************
* Author: Isai Damier
* Title: Recursive Binary Search
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
* Given a sorted array and an element, find the index of the element.
* Return -1 otherwise.
*
* Time Complexity: O(lg n)
* where n is the size of the array
*
* Sample Input: {1,2,3,5,7,8,11,13,17,19,21}; 11
* Sample Output: 6
*
* Technical Details: This is among the most intuitive algorithms in
* the world. And yet many experts have historically gotten it
* wrong (i.e. your nearest textbook may have it wrong). The idea
* is to continuously split the array until the element is found
* (or not).
*
* Because binary search is a tail-recursive algorithm (i.e.
* recursion is the last line in the method), we could also solve
* the problem using iteration as in
* http://www.geekviewpoint.com/java/search/binary_search_iterative
*
**********************************************************************/
public int binarySearchRecursive(int[] A, int el) {
return binarySearchRecursive(A, 0, A.length - 1, el);
}
private int binarySearchRecursive(int[] A, int min, int max, int el) {
if (min <= max) {
int mid = min + (max - min) / 2;
if (el == A[mid]) {
return mid;
} else if (el > A[mid]) {
return binarySearchRecursive(A, mid + 1, max, el);
} else {
return binarySearchRecursive(A, min, mid - 1, el);
}
}
return -1;
}
package algorithms;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;
public class SearchAlgorithmsTest {
/**
* Test of binarySearchRecursive method, of class SearchAlgorithms.
*/
@Test
public void testBinarySearchRecursive() {
System.out.println("binarySearchRecursive");
int[] A = {1,2,3,5,7,8,11,13,17,19,21};
int el = 11;
SearchAlgorithms instance = new SearchAlgorithms();
int expResult = 6;
int result = instance.binarySearchRecursive(A, el);
assertEquals(expResult, result);
el=21;
expResult = 10;
result = instance.binarySearchRecursive(A, el);
assertEquals(expResult, result);
el=1;
expResult = 0;
result = instance.binarySearchRecursive(A, el);
assertEquals(expResult, result);
el=19;
expResult = 9;
result = instance.binarySearchRecursive(A, el);
assertEquals(expResult, result);
el=55;
expResult = -1;
result = instance.binarySearchIterative(A, el);
assertEquals(expResult, result);
}
}
