算法刷题笔记【数组】01
数组理论
数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
注意
数组下标都是从0开始的。
数组内存空间的地址是连续的
因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
数组例题
704.二分查找
题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
分析过程
【文字太长不看系列：↓直接跳到末尾查看打印出循环过程的代码便于理解】
循环不变量
区间定义后，每次改变区间后，区间性质不能变：保持 左闭右闭[a, b] / 左闭右开[a, b)，处理规则要按照区间定义来写，使得每次操作的范围划分满足区间的定义。
1.左闭右闭 [a, b]
while(left ?? right)
分析：如何判断问号处该使用小于(<)号还是小于等于(<=)号？
例如：当下标区间为[x,x]时，此时区间长度为1，区间内只有一个元素。while判断条件若使用"<="，则 left=nums[x]，right=nums[x]，此时条件 left<=right 成立，能使得进入循环的区间满足循环不变；若使用"<"，left=nums[x]，right=nums[x]，此时条件 left<right 不成立，无法使进入循环的区间满足循环不变。
简单来看，闭区间，左边界==右边界是有意义的，因此判断条件可以写成 left <= right。
target < nums[mid] 时如何更新右边界 right
分析：右边界更新为 mid 还是 mid - 1？
若目标值小于二分后的中值，即 target < nums[mid]，则 nums[mid] 一定不在要查找的范围内，不可能为要查找的目标值，即 target!=nums[mid]。此时更新右边界值，right 的正确更新方式为 right = mid - 1，而非 right = mid，否则就将不属于查找范围中的值 nums[mid] 包含了进来。若错误采用了 right < mid 写法，紧接下来的循环可能不会立即导致错误，但当程序运行到二分区间只剩一个元素时，很可能时本该被查到的目标值因为不满足 left < right 条件而退出循环，导致最终找不到目标值。
target > nums[mid] 时如何更新左边界 left
分析：左边界更新为 mid 还是 mid - 1？
由右边界更新方式同理可知，nums[mid] 不在区间中，左边界更新只需 left = mid + 1 。
2.左闭右开[a, b)
while(left ?? right)
分析：如何判断问号处该使用小于(<)号还是小于等于(<=)号？
例如：当下标区间为[x,x)时，此时区间长度为1，区间内只有一个元素。while判断条件若使用"<="，则表示可以有 left=nums[x]，right=nums[x]，此时条件 left<=right ，不能使得进入循环的区间满足循环不变；若使用"<"，left=nums[x]，right=nums[x+1]，此时条件 left<right 成立，使进入循环的区间满足循环不变。
简单来看，闭区间，**左边界==右边界 **是有意义的，因此判断条件可以写成 left <= right。
target < nums[mid] 时如何更新右边界 right
分析：右边界更新为 mid 还是 mid - 1？
若目标值小于二分后的中值，即 target < nums[mid]，则 nums[mid] 一定不在要查找的范围内，不可能为要查找的目标值，即 target!=nums[mid]。此时更新右边界值，right 可更新为 right = mid ，表示取不到 mid ，而非 right = mid - 1，否则就将应该属于查找范围中的值 nums[mid - 1] 剔除了。
target > nums[mid] 时如何更新左边界 left
分析：左边界更新为 mid 还是 mid - 1？
由1中闭区间更新方式，同理可知，nums[mid] 不在区间中，左边界更新仍为 left = mid + 1 。
小结
将数组区间和数学数列中的区间联系起来也很好理解。
左闭右闭方式，将一个完整区间分为3部分 （<t, =t, >t），最终左右边界会相等，指向最后一次查找的位置；
左闭右开方式，将一个完整区间分为2部分 （<t, >=t），该方式左右边界不会有相等的情况，只会相邻。
