CSC236 Data Structures - Binary Search

Binary Search

public class BinSearchTest {
    public static void main(String[] args) {
        int values[] = {2,5,7,8,11,15,22,29,40,43,69,80};
        int loc;

        loc = Search.binarySearch(values,12,43);
        if (loc != -1)
            System.out.println("Number 43 was found in location " + loc);
        else
            System.out.println("Number 43 is not in the array");

        loc = Search.binarySearch(values,12,6);
        if (loc != -1)
            System.out.println("Number 6 was found in location " + loc);
        else
            System.out.println("Number 6 is not in the array");
    }
}

public class Search {

//  searches arr for value
//      size is number of elements in arr
//      assumes arr[first] <= arr[first+1] <= ... <= arr[last]
//      if value is in arr, returns loc where value was found
//      if value is not in arr, returns -1
    public static int binarySearch(int arr[], int size, int value) {
        return recBinSearch(arr, 0, size-1, value);
    }

    private static int recBinSearch(int arr[],int first,int last,int value) {
        if (first > last)
            return -1;
        else {
            int mid = (first + last) / 2;
            if (value == arr[mid])
                return mid;
            else if (value < arr[mid])
                return recBinSearch(arr,first,mid-1,value);
            else
                return recBinSearch(arr,mid+1,last,value);
        }
    }
}

Output


Number 43 was found in location 9
Number 6 is not in the array