Test cases for Binary search might not be something you have already written, but the implementation must be an old exercise you may have do...


Test Cases
Test cases for this is not that specific to binary search, but mostly for any search. However as this search is executed in half by half approach, I wrote a number of test cases to search for the values in first, last, middle indexes followed by an all index search. Also since the array division is changing based on whether array length is odd or even, two test cases are added for that.Here are the names of the test cases.
- shouldReturnFalseIfArrayIsEmpty()
- shouldReturnFalseIfNotFoundInSortedOddArray()
- shouldReturnFalseIfNotFoundInSortedEvenArray()
- shouldReturnTrueIfFoundAsFirstInSortedArray()
- shouldReturnTrueIfFoundAtEndInSortedArray()
- shouldReturnTrueIfFoundInMiddleInSortedArray()
- shouldReturnTrueIfFoundAnywhereInSortedArray()
- shouldReturnFalseIfNotFoundInSortedArray()
Above names are a bit self-explanatory, please see the following code for details.
package com.digizol.algorithms;
import static org.junit.Assert.*;
import org.junit.*;
public class BinarySearchTest {
private BinarySearch sut;
@Before
public void setUp() throws Exception {
sut = new BinarySearch();
}
@Test
public void shouldReturnFalseIfArrayIsEmpty() {
assertEquals(false, sut.find(new int[] {}, 1));
}
@Test
public void shouldReturnFalseIfNotFoundInSortedOddArray() {
assertEquals(false,
sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 }, 9));
}
@Test
public void shouldReturnFalseIfNotFoundInSortedEvenArray() {
assertEquals(false,
sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 },
9));
}
@Test
public void shouldReturnTrueIfFoundAsFirstInSortedArray() {
assertEquals(true,
sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 }, 0));
}
@Test
public void shouldReturnTrueIfFoundAtEndInSortedArray() {
assertEquals(true,
sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 }, 16));
}
@Test
public void shouldReturnTrueIfFoundInMiddleInSortedArray() {
assertEquals(true,
sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 }, 8));
}
// covers the 'true' cases above
@Test
public void shouldReturnTrueIfFoundAnywhereInSortedArray() {
int[] sorted = new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 };
for (int i = 0; i < sorted.length; i++) {
assertEquals(true, sut.find(sorted, sorted[i]));
}
}
// covers the 'false' cases above
@Test
public void shouldReturnFalseIfNotFoundInSortedArray() {
int[] sorted = new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 };
assertEquals(false, sut.find(sorted, sorted[0] - 1));
for (int i = 0; i < sorted.length; i++) {
assertEquals(false, sut.find(sorted, sorted[i] + 1));
}
}
}
Production Code
I want to stress the importance of you trying yourself to complete the code yourself rather than directly going to the code below.I wrote below recursion based production code which passes against above test cases. There are three comments in the code, which helps you to remember the logic easily.
package com.digizol.algorithms;
public class BinarySearch {
public boolean find(int[] sortedValues, int value) {
return search(sortedValues, value, 0, sortedValues.length - 1);
}
private boolean search(int[] sorted, int value,
int leftIndex, int rightIndex) {
// 1. index check
if (leftIndex > rightIndex) {
return false;
}
// 2. middle index
int middle = (rightIndex + leftIndex) / 2;
// 3. recursive invoke
if (sorted[middle] > value) {
return search(sorted, value, leftIndex, middle - 1);
} else if (sorted[middle] < value) {
return search(sorted, value, middle + 1, rightIndex);
} else {
return true;
}
}
}
COMMENTS