Tuesday, December 2, 2014

Binary Search in an Array

Input is an sorted array and an element which need to be searched in the array. The module will return the possition of the element in the given array.

public class BinarySearchArray {
    private final static int Default = -999; //default value
   
    public int BinarySearch(ArrayList<Integer> input, int element)    {
        if(input.size() == 0)
            return Default;
        return BinarySearchRecursive(input, element, 0, input.size());
    }
   
    private int BinarySearchRecursive(ArrayList<Integer> input, int element, int min, int max)    {
        int possition = Default;
        int check_possition = min+((max-min)/2);
        if(input.get(check_possition) == element)
            possition = check_possition;
        else if(max <= min)
            return Default;    //element not found
        else if(element > input.get(check_possition))    {
            int difference = (max-min)/2;
            if(difference == 0) difference = 1;
            min = min + (difference);
            possition = BinarySearchRecursive(input, element, min, max);
        }    else    {
            max = check_possition-1;
            possition = BinarySearchRecursive(input, element, min, max);
        }
        return possition;
    }
}
-----------------------------------------------------------------------------------------------------------
Recursion costs more memory. To be more memory efficient we can use a loop instead of recursion.

public class BinarySearchInLoop {
    private final static int Default = -999; //default value
    public int BinarySearch(ArrayList<Integer> input, int element)    {
        if(input.size() == 0)
            return Default;
        else {
        int min = 0;
        int max = input.size();
        while(min <= max) {
            int check_possition = min+((max-min)/2);
            if(input.get(check_possition) == element) {
            return check_possition;
            } else if(element > input.get(check_possition))    {
            int difference = (max-min)/2;
                    if(difference == 0) difference = 1;
                    min = min + (difference);
            } else {
            max = check_possition-1;
            }
            }
        return Default;
        }
    }
}

No comments:

Post a Comment

UA-39217154-2