1. 二分查找

二分查找是一个基础的算法，二分查找就是将查找的键和子数组的中间键做比较，如果被查找的键小于中间键，就在左子数组中继续查找，如果大于中间键就在右子数中查找，否则中间键就是要找的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function binarySearch(arr, key) {
    let left=0;
    let right=arr.length-1;
    while(left <= right){
        let mid = Math.floor((left+right)/2);
        if(arr[mid] === key) {
            return mid;
        }else if(arr[mid]<key){
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return -1;
}

2. 二分查找的变种

2.1 查找第一个与key相等的元素

也就是查找下标最小的与key相等的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function findFirstEqual(arr, key) {
    let left=0;
    let right=arr.length-1;
    while(left <= right){
        let mid = Math.floor((left+right)/2);
        if(arr[mid] >= key) {
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    if(left<arr.length && arr[left] === key) {
        return left;
    }
    return -1;
}

2.2 查找最后一个与key相等的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function findLastEqual(arr, key) {
    let left=0;
    let right=arr.length-1;
    while(left <= right){
        let mid = Math.floor((left+right)/2);
        if(arr[mid] <= key) {
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    if(right<arr.length && arr[right] === key) {
        return right;
    }
    return -1;
}

2.3 查找第一个等于或者大于key的元素(对照2.1)

1
2
3
4
5
6
7
8
9
10
11
12
13
function findFirstEqualOrLarger(arr, key) {
    let left=0;
    let right=arr.length-1;
    while(left <= right){
        let mid = Math.floor((left+right)/2);
        if(arr[mid] >= key) {
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

2.4 查找最后一个等于或者小于key的元素(对照2.2)

1
2
3
4
5
6
7
8
9
10
11
12
13
function findLastEqualOrSmaller(arr, key) {
    let left=0;
    let right=arr.length-1;
    while(left <= right){
        let mid = Math.floor((left+right)/2);
        if(arr[mid] <= key) {
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return right;
}

2.5 查找第一个大于key的元素(对照2.3)

1
2
3
4
5
6
7
8
9
10
11
12
13
function findFirstLarger(arr, key) {
    let left=0;
    let right=arr.length-1;
    while(left <= right){
        let mid = Math.floor((left+right)/2);
        if(arr[mid] > key) {
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

2.6 查找最后一个小于key的元素(对照2.4)

1
2
3
4
5
6
7
8
9
10
11
12
13
function findLastSmaller(arr, key) {
    let left=0;
    let right=arr.length-1;
    while(left <= right){
        let mid = Math.floor((left+right)/2);
        if(arr[mid] < key) {
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return right;
}