二分查找
#LeetCode#算法#二分查找 2023-12-31

二分查找

之前刷的系列题，只记录了两道比较经典的。

后面回顾会添加。

题目

Leetcode 34.在排序数组中查找元素的第一个和最后一个位置

Leetcode 33. 搜索旋转排序数组

LeetCode 34

解题思路

因为是排好序的数组，按二分查找，先找到最左边的符合 target的，再找最右边的。

实现代码

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
func searchRange(nums []int, target int) []int {
        var res = []int{-1,-1}
    if len(nums) == 0{
        return res
    }
    var left,right,mid int = 0, len(nums) - 1, len(nums) / 2
    // 找到 左区间
    for left <= right{
        if nums[mid] < target{
            // 如果中间值小于，证明 [left,mid] 都小于
            left = mid + 1
        }else{
            // 如果中间值大于，证明 [mid, right] 都大于
            right = mid - 1
        }
        mid = (left + right) / 2
    }
    // 这里是没找到
    if left == len(nums){
       return res
    }
    res[0] = left
    left,right,mid = 0, len(nums) - 1, len(nums) / 2
    // 找到 右区间
    for left <= right{
        if nums[mid] <= target{
            // 如果中间值小于等于，证明 [left,mid] 都小于等于
            left = mid + 1
        }else{
            // 如果中间值大于，证明 [mid, right] 都大于
            right = mid - 1
        }
        mid = (left + right) / 2
    }
    res[1] = right
    // 也是没找到的特殊情况
    if res[0] > res[1]{
        return []int{-1,-1}
    }
    return res
}

LeetCode 33

解题思路

最重要的思路是：将数组一分为二，则一分为二的两个数组，一个必定是有序的，一个必定是无序的。

实现代码

二分实现

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
func search(nums []int, target int) int {
    left,right := 0, len(nums) - 1
    var mid int
    for left <= right{
        mid = (left + right) / 2
        if nums[mid] == target{
            return mid
        }else if nums[left] <= nums[mid]{
            // 这里有一个特殊情况是 nums[left] == nums[mid]
            // 如测试用例 [3,1]，如果归到 else 情况中的话，另外一边是无序的就会导致找不到答案
            // 可以调整顺序，但为了方便理解为什么写在 else if 条件中
            // 如果这部分是有序的，就在这部分查找
            if nums[left] <= target && target < nums[mid]{
                // 在此范围内，更新下界
                right = mid - 1
            }else{
                // 在另一部分无序的范围中
                left = mid + 1
            }
        }else{
            // 上面的条件都不成立，也就是说 right-mid 这部分有序
            if nums[mid] < target && target <= nums[right]{
                left = mid + 1
            }else{
                right = mid - 1
            }
        }
    }
    return -1
}