704. 折半查找（二分）
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ， 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
注意 此题说明是查找，那么数组中一定有target数，所以，我写了if(target==nums[mid]){
return mid;//返回数组下标
}
int search(int* nums, int numsSize, int target){//nums是数组，size是数组的大小，target是需要查找的值 int low,high,mid;//low左边，high右边，mid中间 low = 0;//赋初值，指向最左 high = numsSize-1;//指向最右 while(low<=high){//这里写的不一样，会直接影响后面代码 mid = low+(high-low)/2;//为了防止溢出 if(target==nums[mid]){ return mid;//返回数组下标 } if(target>nums[mid] ){ low = mid+1; } if(target<nums[mid]){ high = mid -1; } } return -1; }
折半插入（二分）
基本思想
折半插入排序，又称二分插入排序，先用折半查找1找到应该插入的位置，再移动元素
步骤（从小到大排序）
找到没有排序的元素
标记元素
对前面排好序的元素进行折半，low、high 上下界，mid标记为中间的元素
将标记元素与 mid 位置上的元素进行比较，如果标记元素<mid 位置上的元素，则应该插入到mid 的左边，high=mid-1；如果标记元素>mid 位置上的元素，则应该插入到 mid 的右边，low=mid+1。重复第3步
当 low>high 时停止折半查找，将[low，i-1]内的元素全部右移，并将标记元素插入到 low 所指的位置
例如：有数组nums = [-1,0,3,9];插入元素x= 5；
示意图：
void blnsertsort(int* nums, int numsSize, int x) { int low = 0; int high = sumSize - 1; int mid = 0; while (low <= high) { mid = low + (high - low) / 2;//防止溢出 if (x > nums[mid]) low = mid + 1; else//x小于后者等于nums[mid] high = mid - 1; } //此时high<low;high+1为插入位置 for (int i = sumSize - 1; i > high; --i) {//后移 nums[i + 1] = nums[i]; } nums[high + 1] = x;//c插入x }
*个人理解，如有不同见解，敬请指出！
