leetCode题解之寻找插入位置

1、问题描述

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

给定一个排好序的数组和一个数，找出这个数在有序数组中位置。

2、问题分析

采用二分法查找，如果该数在数组中，则返回下标。如果查找结束，该数不在数组中，则返回当前下标 +1

3、代码

 1 int searchInsert(vector<int>& nums, int target) {
 2         if( nums.size() == 0)
 3             return 0;
 4         int left = 0,right = nums.size() - 1;
 5         while(left <= right)
 6         {
 7             int mid = (left+right) / 2;
 8             if( nums[mid] == target)
 9                 return mid;
10             else if( nums[mid] > target)
11                 right = mid -1;
12             else
13                 left = mid + 1 ;
14        }
15         return right+1;
16     }