[LeetCode-35]-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.

Example 1:
Input: [1,3,5,6], 5
Output: 2

Example 2:
Input: [1,3,5,6], 2
Output: 1

Example 3:
Input: [1,3,5,6], 7
Output: 4

Example 4:
Input: [1,3,5,6], 0
Output: 0

【难度】Easy

Solution

该题是一个典型的查找问题，可以采用从前到后顺序遍历的方法，也可以采用经典的二分查找算，下面是使用这两种方法的对应代码。

1. 顺序遍历

C++程序中数据存在在vector中，所以可以直接使用下标进行访问。

int searchInsert(vector<int>& nums, int target) {
   int i = 0;
   while(i < nums.size())
   {
       if (target <= nums[i]) break;
       i ++;
   }
   return i;
}

最开始写出该方法后，不相信这么简单，自己想了好几个测试用例，没问题才提交的，通过了，不过效率不高，运行结果如下。

2. 算法改进 – 二分查找

vector可以使用下标操作，同时是有序的，所以可以方便的使用二分查找算法进行查找。

二分查找算法太经典和常用，应熟稔于心。

int searchInsert(vector<int>& nums, int target)
{
      int low = 0;
      int high = nums.size() - 1;

      while(low <= high) //这里的判断条件需要注意
      { 
          int mid = (low + high)/2;

          if(target < nums[mid]) high = mid -1;
          else if(target > nums[mid]) low = mid + 1;
          else return mid;
      }
      return low;
}

上面的算法中，几个判断的地方需要注意下，while中的应该是 low <= high， if判断中举出一个例子就能清楚的看到是咋回事请。

该算法的提交结果：