/***********************************************************************
* Author: Isai Damier
* Title: Iterative 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 achieved by continuously doing the same
* process on ever smaller size of the problem, the solution can
* also be defined using recursion.
* _
* |
* | bs(A[1...n/2-1],el) if el < A[n]
* bs(A[1...n],el) = | bs(A[n/2+1...n],el) if el > A[n]
* | n if el == A[n]
* |_
*
* see implementation at
* http://www.geekviewpoint.com/java/search/binary_search_recursive
*
**********************************************************************/
public int binarySearchIterative(int[] A, int el) {
int min = 0, max = A.length - 1, mid;
while (min <= max) {
mid = min + (max - min) / 2;
if (el == A[mid]) {
return mid;
} else if (el > A[mid]) {
min = mid + 1;
} else {
max = mid - 1;
}
}//while
return -1;
}
package algorithms;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;
public class SearchAlgorithmsTest {
/**
* Test of binarySearchIterative method, of class SearchAlgorithms.
*/
@Test
public void testBinarySearchIterative() {
System.out.println("binarySearchIterative");
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.binarySearchIterative(A, el);
assertEquals(expResult, result);
el=21;
expResult = 10;
result = instance.binarySearchIterative(A, el);
assertEquals(expResult, result);
el=1;
expResult = 0;
result = instance.binarySearchIterative(A, el);
assertEquals(expResult, result);
el=19;
expResult = 9;
result = instance.binarySearchIterative(A, el);
assertEquals(expResult, result);
el=55;
expResult = -1;
result = instance.binarySearchIterative(A, el);
assertEquals(expResult, result);
}
}
