BinarySearch.java

/**
 * 最简单的二分查找:数据有序且唯一
 */

public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {//"<="
        int mid = (low + high) / 2;//low + ((high - low) >> 1)
        if (a[mid] == value) {
            return mid;
        } else if(a[mid] < value){
            low = mid + 1;
        }else{
            high = mid -1;
        }
    }
    return -1;
}
/**
 * 最简单二分查找的递归实现
 */
public int bsearch(int[] a, int n, int val) {
    return bsearchInternally(a, 0, n - 1, val);
}
private int bsearchInternally(int[] a, int low, int high, int value) {
    if (low > high) {
        return -1;
    }
    int mid = low + ((high - low) >> 1);
    if (a[mid] == value) {
        return mid;
    } else if (a[mid] < value) {
        return bsearchInternally(a, mid + 1, high, value);
    } else {
        return bsearchInternally(a, low, mid - 1,value);
    }
}

/**
 * 查找第一个值等于给定值
 */
public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] >= value) {
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    if (low < n && a[low] == value) {
        return low;
    }else{
        return -1;
    }
}

public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] >= value) {
            high = mid - 1;
        }else if(a[mid] < value){
            low = mid + 1;
        }else{
            if((mid == 0) || (a[mid - 1] != value)){
                return mid;
            }else{
                high = mid - 1;
            }
        }
    }
    return -1;
}

/**
 * 查找最后一个值等于给定值的元素
 */
public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] >= value) {
            high = mid - 1;
        }else if(a[mid] < value){
            low = mid + 1;
        }else{
            if((mid == n - 1) || (a[mid + 1] != value)){
                return mid;
            }else{
                low = mid + 1;
            }
        }
    }
    return -1;
}

/**
 * 查找第一个大于等于给定值的元素
 */
public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] >= value) {
            if((mid == 0) || (a[mid - 1] < value)){
                return mid;
            }else{
                high = mid - 1;
            }
        }else{
            low = mid + 1;
        }
    }
    return -1;
}
/**
 * 查找最后一个小于等于给定值的元素
 */
public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] > value) {
            high = mid - 1;
        }else{
            if((mid == n - 1) || (a[mid + 1] > value)){
                return mid;
            }else{
                low = mid + 1;
            }
        }
    }
    return -1;
}