?
目录
?
数组
数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
注意
- 数组下标是从0开始的
- 数组的地址是连续的
- 在删除或者增加数组元素时，数组元素不能删除只能覆盖，所以要移动元素
二分查找
使用条件
- 数组元素要有序的
- 有的题也会出现有重复元素的情况
二分法的边界问题比较重要，关于区间的定义一般有两种，一种是左闭右闭[left,right]，第二种左闭右开[left,right)，这就涉及到循环条件和right值的处理不同
mid防止溢出：
左闭右闭[left,right]：int mid = left + ((right - left) / 2);
左闭右开[left,right)：int mid = left + ((right - left) >> 1);
方法
以LeetCode?704.二分查找为例
给定一个?n?个元素有序的（升序）整型数组?nums 和一个目标值?target ?，写一个函数搜索?nums?中的 target，如果目标值存在返回下标，否则返回 -1。
1.左闭右闭[left,right]
target在[left,right]区间内，所以left=right是有意义的，所以，循环条件和right值的处理：
- while (left <= right)?
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target（因为右面是闭区间，所以target和left比较过了），那么接下来要查找的左区间结束下标位置就是 middle - 1
例：查找元素1
704.二分查找的Java代码
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) / 2); //为了防止溢出，和（left+right）/2一样
if(nums[mid] < target) {
left = mid + 1;
}else if(nums[mid] > target) {
right = mid - 1;
}else if(nums[mid] == target) {
return mid;
}
}
return -1;
}
}2.左闭右开[left,right)
target在[left,right)区间内，所以left=right没有意义的，所以，循环条件和right值的处理：
- while (left <right)?
- right要指向nums.length
- if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle] （因为右区间是开的，所以如果right更新为middle-1，就比较不到当前的right值了。在左区间进行寻找）
例：查找1元素
704.二分查找的Java代码
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + ((right - left) >> 1); //为了防止溢出
if(nums[mid] < target) {
left = mid + 1;
}else if(nums[mid] > target) {
right = mid;
}else if(nums[mid] == target) {
return mid;
}
}
return -1;
}
}35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
上面的母题会了之后，这道题就很简单了，思路基本一样，唯一的不同就是当目标值不存在时函数的返回值。这里也可以讨论两种区间的情况。
1.左闭右闭[left,right]
前面的思路一样，现在来还原最差的情况（最后一次循环）：目标值不存在。例：查找元素2
模拟最后一次left=right的循环，mid指向的值小于目标值2，所以left会更新为mid+1，此时的值就是目标值应该在的位置，让函数值返回left。找目标值7的时候同理。
Java代码
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + ((right - left) / 2);
if(target < nums[mid]) {
right = mid - 1;
}else if (target > nums[mid]) {
left = mid + 1;
}else {
return mid;
}
}
return left; //或者return right+1;
}
}2.左闭右开[left,right)
还原最差的情况（最后一次循环）：目标值不存在，例：查找元素7?
此时是最后一次循环的情况，mid指向的值小于目标值，所以left会向右移一位，所以，函数的返回值是left/right均可。
Java代码
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length;
while(left < right){
int mid = left + ((right - left) >> 1);
if(target < nums[mid]) {
right = mid;
}else if (target > nums[mid]) {
left = mid + 1;
}else {
return mid;
}
}
return right; //或者return left;
}
}?
?
?
?
?
?