[代码随想录]Day01-数组part01

WtcSky / 2023-07-26 / 原文

题目：704. 二分查找

思路：

二分查找一般是在有序的数组中查找指定的值，单纯的查找值，把数组跑一遍的复杂度为O(n)。

二分查找每次把范围缩小一半，我们每次都去中间的值，有以下三种情况：

如果mid位置的值比target大，那么target应该在mid左侧的位置(由小到大排序情况下)
如果mid位置的值比target小，那么target应该在mid右侧的位置(由小到大排序情况下)
如果mid位置的值等于target，返回mid

分治的思想不断重复上述过程(for循环)直到left和right达到某种状态停止，此时如果没有返回，说明数组内没有目标值，二分的时间复杂度为O(log2N)

二分查找法一般又分为两种：左闭右闭以及左闭右开，即[left,right]以及[left,right)。

当在[left,right]中查找目标值时，left=right是有意义的(理解为[1,1]是有意义的)，因此不能忽略掉。
1. 结束条件为for left <= right；
2. 当x[mid] < target时，mid所在位置不是目标值，left又是闭区间本身是具有意义，因此left = mid + 1 而不是left = mid；
3. 当x[mid] > target时，mid所在位置不是目标值，right又是闭区间本身具有意义，因此right = mid - 1而不是right = mid
当在[left,right)中查找目标值时，left=right无意义(理解为[1,1)是有无意义的)，因此可以忽略掉。
1. 结束条件为for left < right；
2. 当x[mid] < target时，mid所在位置不是目标值，left又是闭区间本身是具有意义，因此left = mid + 1 而不是left = mid；
3. 当x[mid] > target时，mid所在位置不是目标值，同时right是开区间本身无意义，因此right = mid而不是right = mid-1(如果right = mid - 1那么mid-1就不会被查找到)

代码：

func search(nums []int, target int) int {
    left,right := 0,len(nums)
    for left < right { // 左闭右开
        mid := left + ((right - left) >> 1) // 取中间值优化版
        if nums[mid] == target { // 找到目标值返回位置
            return mid
        }
        if nums[mid] < target {  
            left = mid + 1
        }else if nums[mid] > target {
            right = mid
        }
    }
    return -1 // 没有找到值返回-1
}

补充：

有两点可以优化的地方：

(right + left) / 2的操作可以用位运算来进行会优化一点(right + left) >> 1。
right + left的操作可能会超出数据范围，因此可以left + ((right - left) >> 1)用减法再加法来避免。

参考：

文章讲解

视频讲解

题目：27. 移除元素

思路：

27.移除元素-双指针法.gif

双指针法解决问题，慢指针实际上维护的是一个没有目标元素的数组(逻辑上)，而快指针是遍历先前的数组。因此当快指针遍历到目标元素时，慢指针不采取任何行动因为自己的数组中不存在该元素；当元素不是目标元素时，慢指针维护自己的数组。

因为慢指针在快指针左侧，所以不会影响到先前数组的元素，不需要担心。

代码：

func removeElement(nums []int, val int) int {
    l := 0 // 慢指针
    lens := len(nums) // 元素数量
    for r := 0; r < len(nums); r++ { // 遍历指针(快指针)
        if nums[r] == val { // 如果等于那就元素数量-1，慢指针不动
            lens--
            continue
        }
        nums[l] = nums[r] // 如果不等于把快指针的值赋给慢指针
        l++
    }
    nums = nums[:lens] // 删除多余的元素
    return lens
}