凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 35. Search Insert Position

分类:algorithm| 发布时间:2016-09-27 00:02:00


题目

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.

Here are few examples.

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

题意

给出一个有序数组以及一个数字,返回等于给定数字的下标或者返回这个数字应该插入的下标。

可以假定数组中没有重复的数字。

比如:

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

解法

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size(), mid;

        while (left < right) {
            mid = (left + right) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
};