代码随想录-数组

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也行
}

1.2.3 巧妙变体练习

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