Binary Search given sorted array Unit test I have implemented Binary search code for a given sorted array, written unit test too, Please review my BST unit test code and let me know your comments for improvements.

class BinarySearch {
    public int binSearch(int[] sortedArray, int key) {
        return search(0, sortedArray.length - 1, key, sortedArray);
    }

    private static int search(int start, int end, int key, int[] sortedArray) {
        int mid = start + ((end-start)/2);

        if (mid &gt;= start &amp;&amp; mid &lt;= end) {
            if (sortedArray[mid] == key) {
                return mid;
            } else if (sortedArray[mid] &gt; key) {
                return search(start, mid-1, key, sortedArray);
            } else if(sortedArray[mid] &lt; key){
                return search(mid+1, end, key, sortedArray);
            }
        }

        return -1;
    }
}

public class BinarySearchTest {

    private BinarySearch binarySearchCUT;
    private static final int UNSUCCESSFUL = -1;

    @Before
    public void setUp(){
        binarySearchCUT = new BinarySearch();
    }

    @Test
    public void testShouldReturnUnsuccessfulOnEmptyArray() {
        assertEquals(UNSUCCESSFUL, binarySearchCUT.binSearch(new int[]{}, 0));
    }

    @Test
    public void testShouldReturnUnsuccessfulOnLeftBound() {
        assertEquals(UNSUCCESSFUL, binarySearchCUT.binSearch(new int[]{1, 2, 4, 7, 8, 12, 15, 19, 24, 50, 69, 80, 100}, 0));
    }

    @Test
    public void testShouldReturnUnsuccessfulOnRightBound() {
        assertEquals(UNSUCCESSFUL, binarySearchCUT.binSearch(new int[]{1, 2, 4, 7, 8, 12, 15, 19, 24, 50, 69, 80, 100}, 101));
    }

    @Test
    public void testShouldReturnSuccessfulOnLeftBound() {
        assertEquals(0, binarySearchCUT.binSearch(new int[]{1, 2, 4, 7, 8, 12, 15, 19, 24, 50, 69, 80, 100}, 1));
    }

    @Test
    public void testShouldReturnSuccessfulOnRightBound() {
        assertEquals(12, binarySearchCUT.binSearch(new int[]{1, 2, 4, 7, 8, 12, 15, 19, 24, 50, 69, 80, 100}, 100));
    }

    @Test
    public void testShouldReturnSuccessfulOnMid() {
        assertEquals(7, binarySearchCUT.binSearch(new int[]{1, 2, 4, 7, 8, 12, 15, 19, 24, 50, 69, 80, 100}, 19));
    }

    @Test
    public void testShouldReturnSuccessfulOnMidGreaterThanGivenNumber() {
        assertEquals(5, binarySearchCUT.binSearch(new int[]{1, 2, 4, 7, 8, 12, 15, 19, 24, 50, 69, 80, 100}, 12));
    }

    @Test
    public void testShouldReturnSuccessfulOnMidLesserThanGivenNumber() {
        assertEquals(10, binarySearchCUT.binSearch(new int[]{1, 2, 4, 7, 8, 12, 15, 19, 24, 50, 69, 80, 100}, 69));
    }

}
BinarySearch

The BinarySearch class should be public since it contains utility methods that are generally useful. To do this, write public class BinarySearch instead of class BinarySearch.

The binSearch method should be static since it does not access any fields from the BinarySearch class. After all, that class doesn't have any fields that could be accessed. To do this, write public static int binSearch instead of public int binSearch.

When you make the binSearch method static, you no longer need the new BinarySearch() in the unit test. This is good since it sounds weird to have a "new binary search". It's confusing to hear this, since "binary search" is an algorithm and not a countable thing. It makes more sense to speak of "the binary search algorithm", avoiding the word "new". On the other hand, "new house" or "new sheet of paper" sounds much more natural.



The helper method currently is:

private static int search(int start, int end, int key, int[] sortedArray) {


The order of the parameters is not the usual one. Usually the array comes first, before its indexes. In this case, this would mean:

private static int search(int[] sortedArray, int start, int end, int key) {




When you compare your code with the predefined Arrays.binarySearch and the helper function, you can see that the code is quite similar, which is a good sign.

One useful thing that the predefined Arrays.binarySearch does is that if the element is not found, it returns a hint about the index where it would be found. This is useful to see the closest existing value.

BinarySearchTest

Your existing unit tests look good. You can leave out the word test at the beginning of the method names to make the names a little shorter. They are quite long, but that's ok.

There are test cases missing:


An element from the middle cannot be found, for example 5 in [1, 2, 6, 10].
The array contains duplicate values, for example 3 in [1, 2, 3, 3, 3, 3, 3, 3, 3].


In the latter case, it is unspecified whether binSearch should return 2 or 3 or any other index. All you can do in your unit test is to check that `array[binSearch(array, key)] == key.