搜索插入位置（二分查找）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2示例 2:
输入: [1,3,5,6], 2
输出: 1原函数
1int searchInsert(int* nums, int numsSize, int target){
2
3}来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
实现代码（二分查找）
1int searchInsert(int* nums, int numsSize, int target){
2 int max = numsSize-1, min = 0, mid = (max+min)/2;
3
4 while(min <= max){
5 if(nums[mid] == target)
6 return mid;
7 else if(nums[mid] > target)
8 max = mid-1;
9 else
10 min = mid+1;
11 mid = (max+min)/2;
12 }
13
14 if(target < nums[mid])
15 return mid;
16 else
17 return mid+1;
18 }
19}
暴力破解
1int searchInsert(int* nums, int numsSize, int target){
2 for(int i = 0; i < numsSize; i++)
3 if(nums[i] >= target)
4 return i;
5
6 return numsSize;
7}
刚看完题目描述时我想到的就是暴力破解，然后用了点时间写出暴力破解的代码，然后又去简化它，最终完成的就是第二个样式的暴力代码。但是这样暴力破解的代码的时间复杂度为 ，虽然不高，但比起二分查找的 还是要高不少。
二分查找需要递归来配合完成，写出递归的技巧是「只要我们遇到递归，我们就把它想象成一个递推公式，然后找出终止条件，最后将递推公式和终止条件翻译成代码。」例如下面的递归代码。
1int f1 = 1, f2 =2;
2int f(int n){
3 if(n == 1) return 1;
4 if(n == 2) return 2;
5 return f(n-1)+f(n-2);
6}
7
8例如
9 f(4) = f(3)+f(2)
10 f(3) = f(2)+f(1)
11最后算出 f(4) = 5。