今天开始刷题，记录一下 23.12.28

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

解题

func search(nums []int, target int) int {
    length := len(nums)
    left := 0
    right := length - 1
    for(left<= right){
        middle := (left+right)/2
        if nums[middle]>target{
            right= middle -1
        }else if nums[middle]<target{
            left = middle+1
        }else{
            return middle
        }
    }
    return -1
}

总结

典型的二分查找，注意left<=right , right =middle +1 这两个算式就行

在排序数组中查找数的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1 2	输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：

1 2	输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

示例 3：

1 2	输入：nums = [], target = 0 输出：[-1,-1]

题解

// 是通过两次二分查找，分别找到对应的边界
// 主要通过 nums[middle]>target 是否有等于来查找左右的边界
// 如果不理解，可以通过画个图就能明白

// 这个函数得到的是target左边一个数的index
func GetLeftBorder (nums []int,target int ) int {
    length := len(nums)
    left := 0
    right := length - 1
    for(left<=right){
        middle := left + (right - left)/2 //不要写成middle := (left+right)/2，防止内存泄漏
        if nums[middle]>=target{    // 这里是大于等于
            right = middle -1
        }else{
            left = middle +1
        }
    }
    return right  // Right=LeftBorder
}
// 这个函数得到的是target右边一个数的index
func GetRightBorder (nums []int,target int)int {
    length := len(nums)
    left := 0
    right := length - 1
    for(left<=right){
        middle := left + (right-left)/2  
        if nums[middle]>target{   // 这里是大于
            right = middle -1
        }else{
            left = middle +1
        }
    }
    return left  // left=RightBorder
}
func searchRange(nums []int, target int) []int {
    LeftBorder := GetLeftBorder(nums,target)
    RightBorder := GetRightBorder(nums,target)
    // 第一个if已经包含了两个数相等以及不相等的情况 因为两边都是闭区间
    if RightBorder - LeftBorder > 1 {
        return []int{LeftBorder+1,RightBorder-1}
    }else{
        return []int{-1,-1}
    }
}

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。