Java: Binary Search (recursive) & TestCases

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 for Binary search might not be something you have already written, but the implementation must be an old exercise you may have done in your algorithm lessons. May be it is easy for you to write it yourself without referring to examples or helping materials? I think it's time for you to try it yourself if you have not done it for a long time.

Since I wanted to solve a puzzle with binary search, I decided to write binary search myself. If you can not remember what the binary search is; a given value must be searched in a sorted array with the aim of minimizing the number of operations by limiting the search into the left or right half of the array by dividing it into two parts.

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.
  1. shouldReturnFalseIfArrayIsEmpty()
  2. shouldReturnFalseIfNotFoundInSortedOddArray()
  3. shouldReturnFalseIfNotFoundInSortedEvenArray()
  4. shouldReturnTrueIfFoundAsFirstInSortedArray()
  5. shouldReturnTrueIfFoundAtEndInSortedArray()
  6. shouldReturnTrueIfFoundInMiddleInSortedArray()
  7. shouldReturnTrueIfFoundAnywhereInSortedArray()
  8. 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;
        }
    }

}
If you reached here after writing the program yourself, you deserve a round of applause. Congratulation!!!

COMMENTS

BLOGGER

Read More...

Name

About,2,Adsense,3,Ant,1,Apache,3,Axis,3,Blogger,1,Books,1,CentOS,2,Chrome,2,CSS,2,Database,3,Earn Online,3,Eclipse,10,Facebook,1,Firefox,10,Gmail,4,GNU/Linux,9,Google,26,GWT,8,Hardware,2,IE,5,Interesting,15,Internet,14,Java,49,Javascript,7,JBoss,1,Jenkins,1,Log4j,2,Me,6,Microsoft,2,Miscellaneous,1,News,11,Opinion,10,OSGi,1,PHP,1,Productivity,3,Programming,36,Puzzle,3,Security,4,Software,41,Sports,9,Spring,2,Story,6,Subversion,3,TDD,4,Tech,2,Tips,1,Tomcat,6,Tutorial,13,Ubuntu,4,Web application,14,Web Design,2,Web services,3,Windows,10,Yahoo,1,Zip,2,
ltr
item
Digizol: Java: Binary Search (recursive) & TestCases
Java: Binary Search (recursive) & TestCases
https://1.bp.blogspot.com/-UAz5X_Y-KyM/WeJlRrVHQSI/AAAAAAAACOg/T_9alX79kUE8jTWJpluby0xM4iprMya_gCLcBGAs/s1600/search%2Bbinary%2Bwww.digizol.com.jpeg
https://1.bp.blogspot.com/-UAz5X_Y-KyM/WeJlRrVHQSI/AAAAAAAACOg/T_9alX79kUE8jTWJpluby0xM4iprMya_gCLcBGAs/s72-c/search%2Bbinary%2Bwww.digizol.com.jpeg
Digizol
https://www.digizol.com/2013/08/java-binary-search-recursive-testcases.html
https://www.digizol.com/
https://www.digizol.com/
https://www.digizol.com/2013/08/java-binary-search-recursive-testcases.html
true
7440473
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS CONTENT IS PREMIUM Please share to unlock Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy