binary search


See On Github

Data

Contributor

Generic placeholder thumbnail

by n1ghtmare

in java

Source Code

/**
 *
 * @author Dimitar Dimitrov
 */
public class BinarySearch {
    private Comparable[] a;
    
    public BinarySearch(Comparable[] a) {
        this.a = a;
    }
    
    public int getIndexOf(Comparable value) {
        return getIndexOf(value, 0, a.length - 1);
    }
    
    // Running time - O(lg(n))
    // Space - O(1)
    private int getIndexOf(Comparable value, int min, int max) {
        if(max > min) {
            int mid = min + (max - min) / 2;
            if(value.compareTo(a[mid]) > 0) {
                return getIndexOf(value, mid + 1, max);
            }
            else if(value.compareTo(a[mid]) < 0) {
                return getIndexOf(value, min, mid);
            }
            else {
                return mid;
            }
        }
        return -1;
    }
}
import java.util.Arrays;

/**
 *
 * @author Dimitar Dimitrov
 */
public class Simulate {
    public static void main(String[] args) {
        Integer[] numbers = new Integer[] { 1, 3, 7, 12, 15, 35, 77, 101, 179, 351 };
        BinarySearch binarySearch = new BinarySearch(numbers);
        int i = binarySearch.getIndexOf(77);
        
        System.out.println("The Data is:");
        System.out.println(Arrays.toString(numbers));
        System.out.println("Searching for the value 77");
        System.out.println(String.format("The index is: %s", i));
    }
    
    /*
     * The Data is: 
     * [1, 3, 7, 12, 15, 35, 77, 101, 179, 351]
     * Searching for 77
     * The index is: 6
     */
}