一、搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
示例 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
一般通过。
二分查找就是那种，通过一个中间值mid将数组（一般是有序）分两区间，[low,mid)和[mid+1,high) (一般是这样分，但也会根据题目有各种变式)，判断target在哪个区间里，然后不断缩小搜索范围，直到区间只剩下一个数。这个数就算不是target，也是比target小的数字里最大的。
int searchInsert(vector<int>& nums, int target) {
int low=0;
int high=nums.size();
int mid;
while(low<high)
{
mid=(low+high)/2;
if(target==nums[mid])
{
return mid;
}
else if(target>nums[mid])
{
low=mid+1;
}
else if(target<nums[mid])
{
high=mid;
}
‘ }
return low;
}
二、寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1: 输入: [1,3,4,2,2] 输出: 2
示例 2: 输入: [3,1,3,4,2] 输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
这题我在《剑指offer》上看过。因为对空间复杂度的限制，所以不能用哈希表。也不能上来直接就二分法，数组是无序的。
这题有个很关键的地方在于 “包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n）”，假设都没有重复的话，数字区间应该是[1,n+1]才对。根据这个思路，我们可以用二分法把数组分成两部分，用mid区分开。在[1~mid]这个部分进行元素的计数统计，统计总数count如果比mid来的大，说明这个区间里有重复的数字，对[mid+1,high]也是同理，统计其间的数字是否比high-mid来的大。
int countNum(vector<int>& nums,int start,int end) { //用来统计个数的
int count=0;
int len=nums.size();
for(int i=0;i<len;i++)
{
if(nums[i]>=start&&nums[i]<=end)
{
count++;
}
}
return count;
}
int findDuplicate(vector<int>& nums)
{
int low=1;
int high=nums.size()-1; //4
int mid;//2
//分区间[1,2],[3,4]
while(low<=high)
{
//cout<<"查找"<<low<<"到"<<high<<endl;
mid=(high+low)/2;
//cout<<"mid:"<<mid<<endl;
if(high==low)
{
return mid;
}
if(countNum(nums,low,mid)<=(mid-low+1))
{
if(countNum(nums,mid+1,high)>(high-mid))
{
low=mid+1;
}
}
else{
high=mid;
}
}
return -1;
}
