博文中会简要介绍Leetcode P0035题目分析及解题思路。
“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.
以下是Java的题解代码实现。
class Solution {
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0)
return 0;
int left = 0, right = nums.length-1, pos = 0;
while (left <= right) {
int mid = (left+right)/2;
pos = mid;
if (nums[mid] > target)
right = mid-1;
else if (nums[mid] < target)
left = mid+1;
else
return mid;
}
return (nums[pos] >= target)? pos: pos+1;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (nums.size() == 0)
return 0;
int left = 0, right = nums.size()-1, pos = 0;
while (left <= right) {
int mid = (right+left)/2;
pos = mid;
if (nums[mid] > target)
right = mid-1;
else if (nums[mid] < target)
left = mid+1;
else
return mid;
}
return (nums[pos] < target)? pos+1: pos;
}
};