数组中的算法

1.什么是数组

2.数组上的算法

2.1二分查找算法

什么是二分查找算法？

算法步骤

算法时间复杂度

一个问题

例题

题目分析

解题代码

2.2双指针法

什么是双指针法？

例题

题目分析

解题代码

1.什么是数组

数组是在一块连续的内存空间上存储相同类型数据的集合。其实数组也是一种基本的数据结构，也是很多更加高级的数结构的基础，比如栈、队列、哈希表……都可以基于数组实现。

下图展示了一个长度为12的 int 类型的数组：

需要注意的是：

数组的下标是从0开始计数的。
数组在内存空间中的地址是连续的。

2.数组上的算法

因为数组的要求是一块连续的内存空间，所以我们可以利用其连续的特性玩一些算法。

2.1二分查找算法

什么是二分查找算法？

二分查找算法（Binary Search Algorithm）是一种在有序数组中查找某一特定元素的搜索算法。

算法步骤

定义左右两个指针。（这里的指针是形象的说法，代表数字的下标）
计算出中间元素的下标，判断待查找元素与数组中间元素的大小。
如果该特定元素小于中间元素，则在中间元素的左边的区间进行查找；需要更新右指针的值。
如果该特定元素大于中间元素，则在中间元素的右边的区间进行查找；需要更新左指针的值。

算法时间复杂度

这种搜索算法每一次比较都使搜索范围缩小一半，因此其时间复杂度为O(log n)，其中n是数组的长度。

一个问题

整个查找过程在一个循环中进行，在未找到指定元素的情况下，左指针不断向右移，右指针不断向左移，那么循环的结束条件是什么呢？是left < right 还是 left <= right 呢？

怎么写这个循环的结束条件，主要取决于left == right 的情况是否有意义，有意义就写成 <= ，没有意义就写成 < ；那么 left == right 到底有没有意义，主要取决于right指针的定义，right指针的定义决定了待查找的区间是 左闭右闭 还是 左闭右开 的。

例题

题目链接 —— 二分查找 (题目来源于力扣)

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

题目分析

题目表明给定的数组是有序的，并且是升序，也就是说数组中没有重复的元素，因此查找到的下标是唯一的，我们可以考虑使用二分查找算法。

解题代码

写法一：定义左闭右闭区间。当我们定义区间为左闭右闭时，left == right 这种情况是有效的。

// 定义左闭右闭
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size()-1;while(left <= right) //left == right 有意义{int mid = left + (right-left)/2; // 防止溢出if(nums[mid] > target) {right = mid-1;}else if(nums[mid] < target){left = mid+1;}else{return mid;}}return -1;}
};

写法二：定义左闭右开区间。当我们定义左闭右开区间时，left == right 这种情况是没有意义的。

// 定义左闭右开
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size();while(left < right) //left == right 没有意义{int mid = left+(right-left)/2;if(nums[mid] < target){left = mid+1;}else if(nums[mid] > target){right = mid;}else{return mid;}}return -1;}
};

2.2双指针法

什么是双指针法？

双指针法就是用两个指针来标记数组中的元素，能够提高遍历的效率。

我们平时遍历数组的时候，都是使用一个变量来标记数组遍历的位置，但是有些情况下，一个变量不够用，这个时候就可以考虑多使用一个变量；如果还是不够，你甚至还能再增加一个变量来标记。

例题

题目链接 —— 移除元素 (题目来源于力扣)

题目：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

题目分析

题目说要我们原地移除所有数值等于val元素，但是数组是连续的空间，如果在中间移除元素，就需要将后面所有的元素都向前移动一个位置，这样一来时间复杂的会非常大。所以，在解决数组中需要删除元素的时候，我们通常考虑找一个合适的值，使用覆盖来达到删除的目的。

解题代码

解法一：暴力解法

// 暴力解法
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for(int i = 0; i < size; ++i) // 遍历数组，找到需要删除的值{if(nums[i] == val) //就需要移除了{// 从需要删除的值的后面找一个值来覆盖for(int j = i+1; j < size; ++j) {nums[j-1] = nums[j];}i--;size--;}}return size;}
};

解法二：双指针法

// 双指针解法
class Solution {
public:int removeElement(vector<int>& nums, int val) {int fast = 0;int slow = 0;for(fast = 0; fast < nums.size(); ++fast){if(nums[fast] != val)  // 找到不等于val的值放到前面去{nums[slow++] = nums[fast];}}return slow;}
};

双指针法对比与暴力解法，可以看出省略了一个查找替换循环的循环，减少了不必要的重复的查找。因此优化了代码的时间复杂度。