二分查找

类型(需注意while、left/right取值、更新)

  1. 左闭右闭
1
2
3
4
5
6
7
8
9
10
11
12
13
function search(nums: number[], target){
    let left = 0, right = nums.length - 1;
    let mid: number;
    while(left <= right){
        mid = left + ((right - left)>>1);
        if(nums[mid]<target){
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return left;
}
  1. 左闭右开
1
2
3
4
5
6
7
8
9
10
11
12
13
function search(nums: number[], target){
    let left = 0, right = nums.length;
    let mid: number;
    while(left < right){
        mid = left + ((right - left)>>1);
        if(nums[mid]<target){
            left = mid+1;
        }else{
            right = mid;
        }
    }
    return left;
}
  1. 左开右开
1
2
3
4
5
6
7
8
9
10
11
12
13
function search(nums: number[], target){
    let left = -1, right = nums.length;
    let mid: number;
    while(left < right){
        mid = left + ((right - left)>>1);
        if(nums[mid]<target){
            left = mid;
        }else{
            right = mid;
        }
    }
    return right;
}

有序数组中二分查找的四种类型

  1. 第一个大于等于x的下标： low_bound(x) 【某些情况会返回第一个大于x的元素，需要手动对边界情况进行处理】
  2. 第一个大于x的下标：可以转换为第一个大于等于 x+1 的下标 ，low_bound(x+1)
  3. 最后一个一个小于x的下标：可以转换为第一个大于等于 x 的下标 的左边位置, low_bound(x) - 1;
  4. 最后一个小于等于x的下标：可以转换为第一个大于等于 x+1 的下标 的 左边位置,

查找数组中第一个大于等于x的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
function search(nums: number[], target){
    let mid: number;
    let left = 0, right = nums.length;
    while(left < right){
        mid = left + ((right - left) >> 1);
        if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}

leetcode链接

  1. 704. 二分查找 简单
  2. 34. 在排序数组中查找元素的第一个和最后一个位置 中等
  3. 35. 搜索插入位置 简单
  4. 69. x 的平方根 简单
  5. 367. 有效的完全平方数 简单

移除元素

典型写法（快慢指针）

1
2
3
4
5
6
7
8
9
10
function removeElement(nums: number[], val: number) {
    let slowIndex = 0, fastIndex = 0;
    while(fastIndex < nums.length){
        if(nums[fastIndex] !== val){
            nums[slowIndex++] = nums[fastIndex];
        }
        fastIndex++;
    }
    return slowIndex;
}

leetcode链接

  1. 26. 删除有序数组中的重复项 （简单）（第一遍写有点拧巴）
1
2
3
4
5
6
7
8
9
10
11
12
13
function removeDuplicates(nums: number[]): number {
    if(nums.length === 1 || nums.length === 0){
        return nums.length;
    }
    let slowIndex = 0, fastIndex = 1;
    while(fastIndex < nums.length){
        if(nums[slowIndex] !== nums[fastIndex]){
            nums[++slowIndex] = nums[fastIndex];
        }
        fastIndex++;
    }
    return slowIndex+1;
};
  1. 283. 移动零 (简单)
  2. 844. 比较含退格的字符串 （简单）（一次过，但是有点拧巴）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function backspaceCompare(s: string, t: string): boolean {
    let sarr = s.split('');
    let tarr = t.split('');
    let slowIndexs = 0, fastIndexs = 0;
    let slowIndext = 0, fastIndext = 0;
    const Sharp = '#';
    while(fastIndexs < sarr.length){
        if(sarr[fastIndexs] === Sharp){
            if(slowIndexs !== 0){
                slowIndexs--;
            }
        }else{
            sarr[slowIndexs++] = sarr[fastIndexs];
        }
        fastIndexs++;
    }
    while(fastIndext < tarr.length){
        if(tarr[fastIndext] === Sharp){
            if(slowIndext !== 0){
                slowIndext--;
            }
        }else{
            tarr[slowIndext++] = tarr[fastIndext];
        }
        fastIndext++;
    }
    if(slowIndexs !== slowIndext){
        return false;
    }
    for(let i=0;i<slowIndexs;i++){
        if(sarr[i] !== tarr[i]){
            return false;
        }
    }
    return true;
};
  1. 977. 有序数组的平方 （简单）（拧巴）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function sortedSquares(nums: number[]): number[] {
    let slow = 0, fast = nums.length - 1;
    let ans = new Array(nums.length);
    let index = nums.length - 1;
    while(slow<=fast){
        if(Math.abs(nums[fast]) > Math.abs(nums[slow])){
            ans[index] = Math.pow(nums[fast], 2);
            fast--;
        }else{
            ans[index] = Math.pow(nums[slow], 2);
            slow++;
        }
        index--;
    }
    return ans;
};