二分查找

二分查找是最基本的算法，复习了一下发现还有很多根本没有考虑的情况，特别记录一下
1:最基本的二分查找

function binarySearch(arr, k){
  let left = 0;
  let right = arr.length - 1;
  while(left <= right){
    let mid = parseInt((left+right)/2);
    if(arr[mid] == k){
      return mid;
    }else if(arr[mid] < k){
      left = mid + 1;
    }else{
      right = mid - 1;
    }
  }
}

2.1 查找第一个与key相等的元素
　　查找第一个相等的元素，也就是说等于查找key值的元素有好多个，返回这些元素最左边的元素下标。

static int findFirstEqual(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;

    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    if (left < array.length && array[left] == key) {
        return left;
    }
    
    return -1;
}

2.2 查找最后一个与key相等的元素
　　查找最后一个相等的元素，也就是说等于查找key值的元素有好多个，返回这些元素最右边的元素下标。

static int findLastEqual(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;

    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] <= key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    if (right >= 0 && array[right] == key) {
        return right;
    }

    return -1;
}

2.3 查找最后一个等于或者小于key的元素
　　查找最后一个等于或者小于key的元素，也就是说等于查找key值的元素有好多个，返回这些元素最右边的元素下标；如果没有等于key值的元素，则返回小于key的最右边元素下标。

static int findLastEqual(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;

    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] <= key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    if (right >= 0 && array[right] == key) {
        return right;
    }

    return -1;
}

2.4 查找最后一个小于key的元素
　　查找最后一个小于key的元素，也就是说返回小于key的最右边元素下标。

static int findLastSmaller(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;

    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return right;
}

2.5 查找第一个等于或者大于key的元素
　　查找第一个等于或者大于key的元素，也就是说等于查找key值的元素有好多个，返回这些元素最左边的元素下标；如果没有等于key值的元素，则返回大于key的最左边元素下标。

static int findFirstEqualLarger(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;

    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

2.6 查找第一个大于key的元素
　　查找第一个等于key的元素，也就是说返回大于key的最左边元素下标。

static int findFirstLarger(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;

    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] > key) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}