Thursday 3 March 2016

Binary search algorithm : Java code

A binary search or half-interval search algorithm finds the position of a target value within a sorted array.

Step#1 Find the mid_element of array and compare it to target_value.

Step#2 If target_value == mid_element,
                        return position
       If target_value < mid_element,
                        then the search continues on the lower half of the array;
       If target_value > mid_element,
                        then the search continues on the upper half of the array.

Step#3 Repeat the Step#2 (eliminating half of the elements) until the target value is either found, or until the entire array has been searched.

Complexity
Worst case performance O(log n)
Best case performance O(1)
Average case performance O(log n)
Worst case space complexity O(1)

Recursive approach
class Recursive {
    static int binary_search(int[] array,int key,int imin,int imax){
        // test if array is empty
        if (imax < imin) {
            // set is empty, so return value showing not found
            return -1;
        } else {
            // calculate midpoint to cut set in half
            int imid = (imin+imax)/2;

            if (array[imid] > key) {
                // key is in lower subset
                return binary_search(array, key, imin, imid - 1);
            } else if (array[imid] < key) {
                // key is in upper subset
                return binary_search(array, key, imid + 1, imax);
            } else {
                // key has been found
                return imid;
            }
        }
    }
}

public class BinarySearch {
    public static void main(String[] args) {
        int[] array={1,4,5,7,8,9};
        int key=7;
        int idx=Recursive.binary_search(array,key,0,array.length-1);
        System.out.println("Using recursive approach.\n Index# "+idx);
    }
}

Output:
    Using recursive approach.
     Index# 3


Iterative approach
class Iterative {
    int binary_search(int array[], int key, int imin, int imax) {

        while (imin <= imax) {
            int imid = (imin+imax)/2;
            if (array[imid] == key) {
                // key found at index imid
                return imid;
            } else if (array[imid] < key) {
                // change min index to search upper subarray
                imin = imid + 1;
            } else {       
                // change max index to search lower subarray
                imax = imid - 1;
            }
        }
        // key was not found
        return -1;
    }
}

public class BinarySearch {
    public static void main(String[] args) {
        int[] array={1,4,5,7,8,9};
        int key=7;
                
        idx=Recursive.binary_search(array,key,0,array.length-1);
        System.out.println("Using iterative approach.\n Index# "+idx);
    }
}

Output:
    Using iterative approach.
     Index# 3
References:

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...