Binary Search

Binary Search

Recursive

public static int binarySearch(int[] a, int target, int min, int max) {
    if (min > max) {
        return -1;
    }

    // calculate the midpoint for roughly equal partition
    int mid = (min + max) / 2;
    if (mid >= a.length) {
        // Target is greater than the greatest number in the array.
        return -1;
    }

    // determine which subarray to search
    if (a[mid] < target) {
        // change min index to search upper subarray
        return binarySearch(a, target, mid + 1, max);
    } else if (a[mid] > target) {
        // change max index to search lower subarray
        return binarySearch(a, target, min, mid - 1);
    } else {
        // target found at index mid
        return mid;
    }
}

Iteration

public static int binarySearch(int a[], int target, int min, int max) {
    // continue searching while [min, max] is not empty
    while (max >= min) {
        // calculate the midpoint for roughly equal partition
        int mid = (max + min) / 2;
        if (mid >= a.length) {
            break;
        }

        // determine which subarray to search
        if (a[mid] < target) {
            // change min index to search upper subarray
            min = mid + 1;
        } else if (a[mid] > target) {
            // change max index to search lower subarray
            max = mid - 1;
        } else {
            // target found at index mid
            return mid;
        }
    }

    // target not found
    return -1;
}