二分查找及其若干变种

1. 二分查找（找到返回下标，找不到返回-1）

//二分查找
int binarySearch(int arr[], int len, int key)
{
    int left = 0;
    int right = len - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;
        if (key < arr[mid]) {//key在左边
            right = mid - 1;
        } else if (arr[mid] < key) {//key在右边
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

2. 查找最后一个<key的数

//2 查找第一个大于等于key的元素
int findFirstGreaterEqual(int arr[], int len, int key)
{
    int left = 0;
    int right = len - 1;
    int mid;


    while (left <= right) {
        mid = (left + right) / 2;
        if (key <= arr[mid]) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

3. 查找第一个>=key的数

//2 查找第一个大于等于key的元素
int findFirstGreaterEqual(int arr[], int len, int key)
{
    int left = 0;
    int right = len - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;
        if (key <= arr[mid]) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

4. 查找最后一个<=key的数

//2 查找第一个大于等于key的元素
int findFirstGreaterEqual(int arr[], int len, int key)
{
    int left = 0;
    int right = len - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;
        if (key < arr[mid]) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

5. 查找第一个>key的数

//4 查找第一个大于key的元素
int findFirstGreater(int arr[], int len, int key)
{
    int left = 0;
    int right = len - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;
        if (key < arr[mid]) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

0. 通式模板

while (left <= right) {
        mid = (left + right) / 2;
        if (key ? arr[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ?;