四种常见的二分查找变形问题

二分查找是一种高效的查找方法，它的使用前提是元素的顺序有序，并且元素的访问的时间复杂度是O（1），一般情况下数据源中没有重复的数据的时候，我们要查找的某一个数据的位置是唯一的。通常的二分查找写法:

private int erfen(int[] array, int n) {
    int low = 0;
    int high = array.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] == n) {
            return mid;
        } else if (array[mid] < n) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

但是还有如下几种变形的二分查找问题
1.查找第一个值等于给定值的元素
2.查找最后一个值等于给定值的元素
3.查找第一个大于等于给定值得元素
4.查找最后一个小于等于给定值的元素

//二分查找含有重复元素的第一个值所在位置
public int firstErfen(int[] array, int n) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] < n) {
            low = mid + 1;
        } else if (array[mid] > n) {
            high = mid - 1;
        } else {
            if (mid == 0 || array[mid - 1] != n) {
                return mid;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

//二分查找含有重复元素的最后一个所在位置
public int lastErfen(int[] array, int n) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] < n) {
            low = mid + 1;
        } else if (array[mid] > n) {
            high = mid - 1;
        } else {
            if (mid == array.length - 1 || array[mid + 1] != n) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

//二分查找第一个大于等于某个值的位置
public int bSearch1(int[] array, int n) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] >= n) {
            if (mid == 0 || array[mid - 1] < n) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

//二分差值最后一个小于等于某个值的位置
public int bSearch2(int[] array, int n) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] <= n) {
            if (mid == array.length - 1 || array[mid + 1] > n) {
                return mid;
            } else {
                low = mid + 1;
            }
        } else {
            high = mid - 1;
        }
    }
    return -1;
}