代码随想录-数组

1.基础知识

数组的内存分配理论上是连续的，需要特别注意的是别越界就好了。

2.二分查找

力扣题目链接

二分的精髓在于一次搜索缩小一半的搜索范围！！！

基础写法

思路：参考 CSDN二分查找)或代码随想录二分查找，写法比较简单，也已经比较熟悉了，只要注意区间定义的不变，就能解决问题。有递归和非递归两种写法，注意非递归有“左闭右闭”和“左闭右开”两种写法。

// 递归
func BianrySearch(nums []int, target int, left, right int) int {
	//找不到目标元素
	if left > right {
		return -1
	}
	//先查找中间元素
	mid := left + (right-left)/2
	if nums[mid] == target {
		return mid
	} else if nums[mid] < target { //中间元素比目标元素小，那就查找右边区间
		return BianrySearch(nums, target, mid+1, right)
	} else if nums[mid] > target { //中间元素比目标元素大，那就查找左边区间
		return BianrySearch(nums, target, left, mid-1)
	}
	return -1
}

// 左闭右闭[left,rgiht]
func BianrySearch1(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right { //当left == right时，区间[left, right]仍然有效
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		}
	}
	return -1
}

// 左闭右开[left,rgiht)
func BianrySearch2(nums []int, target int) int {
	left, right := 0, len(nums)
	for left < right { //当left == right时，区间[left, right)无效
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid
		}
	}
	return -1
}

题目推荐

搜索插入位置

力扣题目链接
思路：和左闭右闭的二分查找思路几乎完全一样，只是多了对插入位置的判断，需要在找不到target时返回顺序插入的位置。麻烦的理解点在于顺序插入的位置，即找第一个大于target的数的位置，以左闭右开的二分查找为例子——

1. 如果找到target，在循环判断中直接返回mid即可；

2. 如果找不到target，要返回它将会被按顺序插入的位置，l和r会在相遇处跳出循环，，此时可以按照三种情况考虑：

   • target < nums[0]，应插入位置为0，此时l不动，r不断向左移动到0
   • target > nums[len(nums)-1]，应插入位置为len(nums)，此时r不动，l不断向右移动到len(nums)
   • target 位于数组顺序之间，应插入位置看l和r，最后一次[l,r)相邻，mid一定取l
     • nums[mid] < target： l右移，说明mid对应的数小了，刚刚好就小那么一点点
     • nums[mid] > target： r左移，说明mid对应的数大了，刚刚好就大那么一点点

   所以相遇的位置就是顺序插入的位置。想还是很困难啊，真正做的时候还是拿几个例子推理一下。为什么这样写是对的？

// [l,r)，在找不到target的情况下l和r会在相遇处跳出循环
func searchInsert(nums []int, target int) int {
	l, r := 0, len(nums)
	var mid int
	for l < r {
		mid = (l + r) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return r  //返回l也行
}

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := (l+r)/2
        if nums[mid] == target {
            return mid
        }else if nums[mid] < target {
            l = mid + 1
        }else{
            r = mid 
        }
    }
    return r
}

1.2.3 巧妙变体练习

1. 在排序数组中查找元素的第一个和最后一个位置
   链接：
   [该类型的内容暂不支持下载]
   关键点：数组是非递减顺序的，查找思路转换为target是否在数组的大小范围内外的查找；指针移动的条件是二分查找的变体，是用左指针靠近右边界、右指针靠近左边界，所以看起来似乎和二分查找有些许差别
   解题思路：分三种情况进行讨论，用两次查找获取左右边界
   [0034在排序数组中查找元素的第一个和最后一个.go]
   1.3 双指针
   1.4 滑动窗口

1，2，4，4，4，4，5

整体思路

• 使用两个函数，分别寻找左边界和右边界，组成最终答案返回

问题思考

• 一次搜索如何缩小一半的搜索范围？
• 何时停止搜索？
• 如何整理答案？

想要一次搜索缩小一半的搜索范围，需要明确如果mid的数等于target了，它是我想要的索引吗？很显然不一定是（自己举个例子就知道了），那应该如何缩小搜索范围呢？找左边界时，遇到相同元素，我们可以很确定答案只能出现在左边，因为现在已经搜到一个元素了，我们不确定这个元素前面还有没有相同的元素，所以我们只能往前搜，right就要往前移动。同理搜索右边界时，遇到相同元素，left需要左移。这才是这道题目中二分查找最精髓的地方。

何时停止搜索？答案是搜索范围为空时就要停止搜索，这针对左闭右开和左闭右闭两种区间策略而言都是通用的，只要没有元素可以继续搜索了就要停止。

如何整理答案？没有搜索到target时返回-1，搜索到target返回索引。左闭右开的搜索区间导致查找左右边界在最后处理上有些许的不同。实际上查找的还是目标值，不是大一点或者小一点的值，只是没有找到数时表现出找到大一点或者小一点的值。其实这个搜索在数组内明确存在target是一定能够找到数的边界位置。left因为是闭区间，所以跳出循环时一定是正确答案，而right是开区间，最后一次循环时一定会强制让left移动，导致right偏离真实答案一格。