leetcode清晨的算法修炼课——数组（一）彻底掌握二分法

使用数组之前须知数组的存储方式为顺序存储方式，这就需要我们关注以下几点：
1，一维数组a[n]的数组元素存放位置是一片连续的存储空间。
2，二维数组a[m][n]的数组元素存放位置是m片连续的存储空间，因为二维数组可以视为是m个容量为n的一维数组。而该二维数组其实是一个一维数组当中连续存储了m个一维数组的首地址，根据这m个一维数组当中的首地址，即可依次访问这m个一维数组，即访问到所有的数组元素。
3，由于数组在内存中连续存储的特性，所有在删除或者增添元素的时候，就难免要移动其他元素的地址，因此数组不便于在多增删的场景中使用。

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:
输入: [1,3,5,6], 5
输出: 2

示例 2:
输入: [1,3,5,6], 2
输出: 1

示例 3:
输入: [1,3,5,6], 7
输出: 4

示例 4:
输入: [1,3,5,6], 0
输出: 0

#include
#include
using namespace std;

class Solution {

public:
	int searchInsert(vector& nums, int target) {
		int low = 0;
		int high = nums.size()-1;
		while (low <= high)
		{
			int mid = low+((high - low) / 2);
			if (target == nums[mid])
				return mid;
			else if (target < nums[mid])
				high = mid-1;
			else if (target > nums[mid])
				low = mid+1;
		}
		return high + 1;
	}
};
int main()
{
	vectordata;
	data.push_back(3);
	data.push_back(6);
	data.push_back(18);
	data.push_back(19);
	data.push_back(27);
	data.push_back(30);
	Solution obj;
	cout< 
2.1.3 分析 
二分法的难点并不在于算法的理解，该算法是比较好理解的，个人认为难点就在于边界条件的判定，因此我们通过这道题目就此彻底了解清楚二分法算法运行到最后的边界情况。
 
 
2.1.4 总结 
1，二分法是一种查找算法复杂度为O(logn)的一种算法
 2，二分法要求必须是数组这种数据结构，因为只有数组这种顺序表数据结构，我们才可以将其下标看作指针，而下标可以任意计算，因此该算法中要求的mid这种中间指针就可以直接计算出来。如果选择链表或者其他数据结构，mid无法计算。
 3，二分法的好处就在于减小了时间复杂度，因此我们以后遇到有序数组的查找问题时可以考虑使用二分法优化。