0 前言

??昨天结束了《代码随想录》一刷（只看不上机操作，目的是对算法建立初步的认识），历时一个多月。在第一遍阅读之后，有许多不理解的地方，在书中用问号标识。第二遍阅读本书目的就是想通过上机训练将之前的疑惑解开。另外，本书题解和内容仍有一小部分错误，希望在此更正。

1 第一章面试要知己知彼

??本章主要介绍面试流程、如何写简历及代码规范。本书中的C++代码严格按照Google C++编程规范：
????1.操作符左右一定有空格。
????2.分隔符（,和;)的前一位没有空格，后一位有空格。
????3.花括号和函数位于同一行，并且前面有一个空格。
????4.控制语句（while、if、for）后都有一个空格。

2 第二章程序的性能分析

??本章主要介绍时间复杂度分析、程序运行时间、编程语言内存管理和空间复杂度分析。

3 第三章数组

3.1 数组理论基础

??本节介绍数组的基础知识。在写编程题的过程中，我们不但要会使用数组，更要了解数组的一些特性。

?? 1. 数组下标都是从0开始。
?? 2. 数组在内存空间的地址都是连续的。正因如此，所以在删除或添加元素时要移动其他元素的地址。
?? 3. 如果使用C++进行编程，要注意vector和array的区别。（vector的底层实现其实就是array）整理如下：
??vector是顺序容器，其利用连续的内存空间来存储元素，但是其内存空间大小是能够改变的。其能够很方便的管理内存空间并能动态增长内存空间，每次新申请的空间是原有空间大小（即申请后是申请前的2倍）。但是这个能力是有代价的，它耗费了更多的内存空间。与其他顺序容器（deques，lists，forward_lists）相比，vector能更快速地访问元素并且从end位置增加和删除元素相对更高效，但是在其他位置进行插入和删除操作比其他顺序容器在效率上差得多。
??array是顺序容器，其也是利用连续的内存空间来存储元素，但它的内存空间是固定大小的，申请之后就无法改变。array不能存储其定义之外的数据，包括超出其大小尺寸的、非定义类型的数据。0尺寸（zero-sized）的Array是合法的，但是它不能被解引（dereference），即front/back/data操作。Swap操作是一个线性操作（只能交换两个属性相同的array：大小和类型），它分别交换两个数组中的所有元素，是一个比较低效的操作。值得一提的是，在交换之后，迭代器仍可以指向原来的容器（两个array，a和b，两个迭代器it1和it2，it1指向a，it2指向b，a和b进行swap操作；那么it1指向的还是a，但是内容是b的；it2指向的还是b，但是内容是a的）。array容器的独特特性是他们能被看做tuple对象，重载了get函数来像访问tuple一样访问array元素，并重载了独有的tuple_size和tuple_elelment。
??相同点：都能用下标来访问元素。都是顺序容器，采用的是顺序的存储空间。
??不同点：创建方式上不同。vector无需指定大小，只需指定类型，e.g. vector<int> a;。array需要同时指定类型和大小，e.g. array<int, 3> a;；内存使用上不同。vector需要占据比array更多的内存，因为其内存空间大小是动态可变的。array内存是高效的，用多少就申请多少；效率上不同。vector效率偏低，因为当向vector中添加新元素的时候，内存空间不够，需要重新申请更大的空间，由于vector是连续内存空间的，因此其申请更多空间的时候，可能整个位置发生改变，需要将原来空间里的数据拷贝过去；下标类型不同。在用下标访问元素时，vector 使用 vector::size_type 作为下标的类型，而数组下标的正确类型则是 size_t；swap操作不同
vector是将引用进行交换，效率高，其迭代器指向原来的容器（原来的容器中的元素指向的却是另一个容器的值），但是end的引用并没有发生交换，因此在输出的时候注意别用end作为迭代终止条件。 array是进行值的交换，效率低，且迭代器仍指向原来的容器。

?? 4. 二维数组在内存中是连续的。

3.2 二分查找

力扣题号：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]之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
思路
??二分法使用前提条件：元素有序，无重复（否则返回的元素下标可能不是唯一的）。
??二分法虽然逻辑简单，但是边界条件容易在紧张情况下写错。原因主要在于不清楚区间的定义。在本书中，区间的定义就是“不变量”。要在二分查找的过程中保持“不变量”——在while循环中，每一次边界的处理都要根据区间的定义来操作，这就是“循环不变量"规则。
??二分法中区间的定义一般有两种，一种是左闭右闭即[left,right]，另外一种是左闭右开即[left,right）。下面基于这两种区间的定义分别讲解两种不同的二分法写法。

3.2.1 二分法写法（一）

??定义target在[left,right]区间有两个特定：
????1.left和right相等的情况在[left,right]区间是有意义的(右边界right所指元素是实际存在的，例如leftright最后一个元素），所以要在while循环条件中用left<=right。
????2.如果num[middle]大于target，则更新搜索范围右下标right为middle-1.因为当前这个nums[middle]一定不是target，所以接下来要查找的是middle左边的区间，结束下标位置right是middle-1。

题解

class Solution{
	public:
		int search(vector<int>& nums,int target) {
			int left = 0;
			int right = nums.size()-1;//定义target在左闭右闭区间
			while(left <= right){//当left==right时，区间仍然有意义，所以使用<=
				int middle = left + ((right - left) / 2);//防止溢出，等同于（left+right）/2
				if (nums[middle] > target) {
					right = middle - 1;//target在左区间[left,middle-1] 
				} else if (nums[middle] < target) {
					left = middle + 1;//target在右区间[middle+1,right] 
				} else {
					return middle;//找到元素，直接返回下标 
				}
			} 
			return -1;//未找到目标值 
		}
};