Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Search Insert Position

Leetcode algorithms 第 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.

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的位置。对于中间位置mid:

  • 如果A[mid] >= target,那么答案至少应该为mid,或者为mid的左边位置,则ed = mid
  • 否则,即A[mid] < target,那么答案肯定在mid的右边,而且不可能为mid,则st = mid +1

具体代码如下:

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        if (target > A[n-1]) return n;
        
        int st = 0, ed = n - 1;
        while (st < ed)
        {
            int mid = st + (ed - st) / 2;
            if (A[mid] >= target) ed = mid; //大于或等于
            else st = mid + 1;
        }
        return st;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论