1
\$\begingroup\$

I have implemented binary search solution by using recursion and iterative approach.

I there any way to improve it?

Tests

package test;

import main.algorithms.BinarySearchDemo;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class BinarySearchTest {

    BinarySearchDemo binarySearchDemo;
    int[] array;

    @Before
    public void setUp(){
        binarySearchDemo = new BinarySearchDemo();
        array = new int[]{2, 3, 5, 6, 9, 11, 12, 15, 17, 21};
    }

    @Test
    public void testBinarySearchJavaAPI(){
        Assert.assertEquals(2, binarySearchDemo.binarySearchJavaAPI(5,array));
    }

    @Test
    public void testBinarySearchImpl(){
        Assert.assertEquals(2, binarySearchDemo.binarySearchImpl(5,array));
    }

}

Implementation

package main;

public class BinarySearch {

    private static boolean binarySearchRecursive(int[] array, int i) {

        return binarySearchRecursive(array,0,array.length-1,i);
    }

    private static boolean binarySearchRecursive(int[] array, int left, int right, int item) {

        if(left > right){
            return false;
        }
        int pivot =  (right - left) / 2 + left;

        if(item == array[pivot]){
            return true;
        }
        else if ( item < array[pivot] ){
            return binarySearchRecursive(array, left,pivot-1,item);
        }else {
            return binarySearchRecursive(array, pivot+1, right, item);
        }
    }


    private static boolean binarySearchIterative(int[] array, int item) {

        int left = 0;
        int right = array.length - 1 ;

        while (left < right) {
            int mid = (left + right)/2 + left;
            if (array[mid] == item) {
                return true;
            } else if(item < array[mid]) {
                right = mid-1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }

}
\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

You haven't indicated the purpose for writing these implementations. The natural alternative would be to use Arrays.binarySearch unless this is purely for learning purposes.

Testing

Your test suite is far from exhaustive, testing that both methods can find the item at position 2 is very minimal (at the moment both implementations could simply always return 2). Consider adding additional tests for edge cases (end of array being searched, beginning of array being searched for example). Consider what behaviour you're expecting if the item isn't in the array being searched and adding test cases for those scenarios.

array isn't a great name for the source data in your tests. sortedArray or dataToSearch would be a bit better however consider declaring the array in each test method. In a larger test file, scrolling up and down to see the data in the array, versus the test that's being performed adds extra overhead, which can be undesirable.

Implementations

All of your methods are declared as private. Some of them are meant to be called from outside the class, some of them (such as the recursive call) probably aren't. This should be reflected in the access declarations.

Naming is an important aspect of development. The better your names are and the more consistent you are with them, the easier your code is to follow. You're consistent with your use of left and right, but mid is called pivot in the alternate implementation. The item to find is either i or item. IDE's will often give parameter name prompts even when there is no Java Doc. If you name your parameters well, it's clear that the parameters are (int[] arrayToSearch, int itemToFind)

Doh...

I should really have noticed this earlier... but both of your methods return boolean, however you're asserting they both return 2, which isn't a boolean... Think about what you want the method to return...implement that...and write the tests accordingly...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.