# Recursive Binary Searchby Isai Damier, Android Engineer @ Google

```/***********************************************************************
* 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);
}
}```