算法入门--搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

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

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

输入: nums = [1,3,5,6], target = 7
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的写法：

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4      int hig=nums.size()-1;int low =0;int mid=0;
 5      while(low<=hig)
 6      {
 7           mid=(low+hig)/2;
 8          if(target==nums[mid])
 9          {
10              return mid;
11          }
12          else if(target>nums[mid])
13          {
14              low=mid+1;
15          }
16          else 
17          {
18              hig=mid-1;
19          }
20      }
21 if(low>mid)
22 {
23 return low;
24 }
25    
26 return low;
27  }
28 };

但是官方的写法更加厉害

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4         int n = nums.size();
 5         int left = 0, right = n - 1, ans = n;
 6         while (left <= right) {
 7             int mid = ((right - left) >> 1) + left;
 8             if (target <= nums[mid]) {
 9                 ans = mid;
10                 right = mid - 1;
11             } else {
12                 left = mid + 1;
13             }
14         }
15         return ans;
16     }
17 };
18 
19 作者：LeetCode-Solution
20 链接：https://leetcode.cn/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/
21 来源：力扣（LeetCode）
22 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。