二分查找

Posted on | Post modified: |
Words count in article: 797

什么是二分查找：二分查找每次只查询 mid（数组最中间的数），如果没找到目标，就缩小区间，根据 mid 和目标数对比，只搜左半区间或右半区间。

二分查找的前提：数据有序

二分查找结束的条件：查找区间为空，或者找到元素

二分查找的条件分支：

  1. nums[mid]==target
  2. nums[mid]<target
  3. nums[mid]>target

二分查找的搜索区间表示形式：

  1. 左闭右开（区间为空的条件是 left==right）
  2. 左闭右闭（区间为空的条件是 left>right）

二分查找有的时候我会写出死循环来，仔细思考了一下：必须每次收缩边界的时候，都排除掉 mid，完全避免 mid 被重复查的可能。

习题

  1. leetcode 704. 二分查找
  2. leetcode 34. 在排序数组中查找元素的第一个和最后一个位置（中等）

第一题答案：
左闭右闭搜索区间的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length-1;
    while(left<=right){
        const mid = left + Math.floor((right-left)/2);
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]>target){
            right = mid-1;
        }else if(nums[mid]<target){
            left = mid+1;
        }
    }
    return -1;
};

左闭右开搜索区间的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length;
    while(left<right){
        const mid = left + Math.floor((right-left)/2);
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]>target){
            right = mid;
        }else if(nums[mid]<target){
            left = mid+1;
        }
    }
    return -1;
};

第二题答案：
左闭右闭搜索区间的写法：

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
37
38
39
40
41
42
43
44
45
46
47
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    return [findLeft(nums, target), findRight(nums, target)]
};

var findLeft = function(nums, target){
    let left = 0;
    let right = nums.length;
    while(left<right){
        let mid = left + Math.floor((right-left)/2);
        if(nums[mid]==target){
            right = mid;
        }else if(nums[mid]<target){
            left = mid+1;
        }else if(nums[mid]>target){
            right = mid;
        }
    }
    if(nums[left]==target){
        return left
    }
    return -1;
}

var findRight = function(nums, target){
    let left = 0;
    let right = nums.length;
    while(left<right){
        let mid = left + Math.floor((right-left)/2);
        console.log(left, mid, right)
        if(nums[mid]==target){
            left = mid+1;
        }else if(nums[mid]<target){
            left = mid+1;
        }else if(nums[mid]>target){
            right = mid;
        }
    }
    if(nums[right-1]==target){
        return right-1;
    }
    return -1;
}

左闭右闭搜索区间的写法：

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
37
38
39
40
41
42
43
44
45
46
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    return [fundLeft(nums, target), fundRight(nums, target)]
};

var fundLeft = function(nums, target){
    let left = 0;
    let right = nums.length - 1;
    while(left<=right){
        let mid = left + Math.floor((right-left)/2);
        if(nums[mid]==target){
            right = mid-1;
        }else if(nums[mid]<target){
            left = mid+1;
        }else if(nums[mid]>target){
            right = mid-1;
        }
    }
    if(nums[left]==target){
        return left;
    }
    return -1;
}

var fundRight = function(nums, target){
    let left = 0;
    let right = nums.length - 1;
    while(left<=right){
        let mid = left + Math.floor((right-left)/2);
        if(nums[mid]==target){
            left = mid+1;
        }else if(nums[mid]<target){
            left = mid+1;
        }else if(nums[mid]>target){
            right = mid-1;
        }
    }
    if(nums[right]==target){
        return right;
    }
    return -1;
}