首页 > 其他 > 详细

leetcode笔记:Search Insert Position

时间:2015-12-25 21:08:04      阅读:226      评论:0      收藏:0      [点我收藏+]

一. 题目描述

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

二. 题目分析

题目的大意是,给定一个已排序的数组和一个目标值target,如果在数组中找到该目标值,就返回这个目标值的元素下标。如果没有找到,就返回target应该插入到该数组中的位置下标。这个过程中,假设该数组中没有重复元素。

Search for a Range 的解法类似,二分查找即可,可能出问题的地方是对边界条件的处理。

三. 示例代码

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size(), low = 0, high = n - 1, midIndex = 0;
        while (low <= high)
        {
            midIndex = (low + high) / 2;
            if (nums[midIndex] == target)
                return midIndex;
            else if (nums[midIndex] > target)
                high = midIndex - 1;
            else
                low = midIndex + 1;
        }
        // 边界
        if (low > n)
            return n;
        if (high < 0)
            return 0;
    }
};

解题结果:

技术分享

四. 小结

二分查找的经典题目,对边界的情况需要额外考虑。该题实际上是实现:std::lower_bound() 的功能。

leetcode笔记:Search Insert Position

原文:http://blog.csdn.net/liyuefeilong/article/details/50404976

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!