[LintCode/LeetCode] Search Insert Position

cjie 发布于2019-08-14 15:40 / 2255人阅读

Problem

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,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

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

[1,3,5,6], 0 → 0

Challenge

O(log(n)) time

Note

标准二分法题目。

Solution

public class Solution {
    public int searchInsert(int[] A, int target) {
        int start = 0, end = A.length-1, mid;
        if (A == null || A.length == 0) return 0;
        while (start <= end) {
            mid = (start+end)/2;
            if (A[mid] == target) return mid;
            else if (A[mid] < target) start = mid+1;
            else end = mid-1;
        }
        return start;
    }
}

GPU云服务器云服务器 position() position insert position:absolute

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65937.html

[LintCode/LeetCode] Implement Trie

摘要：首先，我们应该了解字典树的性质和结构，就会很容易实现要求的三个相似的功能插入，查找，前缀查找。既然叫做字典树，它一定具有顺序存放个字母的性质。所以，在字典树的里面，添加，和三个参数。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

付永刚 2019-08-14 15:23 评论0 收藏0
[LintCode/LeetCode] Search for a Range [左右边界法/一次循环

摘要：首先，建立二元结果数组，起点，终点。二分法求左边界当中点小于，移向中点，否则移向中点先判断起点，再判断终点是否等于，如果是，赋值给。 Problem Given a sorted array of n integers, find the starting and ending position of a given target value. If the target is not...

zhangrxiang 2019-08-14 15:41 评论0 收藏0
[LintCode/LeetCode] Search in Rotated Sorted Arra

摘要：找中点若起点小于中点，说明左半段没有旋转，否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无，就容易了。还是用二分法优化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...

U2FsdGVkX1x 2019-08-14 15:41 评论0 收藏0
[LintCode/LeetCode] Edit Distance

摘要：构造数组，是的，是的，是将位的转换成位的需要的步数。初始化和为到它们各自的距离，然后两次循环和即可。 Problem Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 s...

snowell 2019-08-14 15:29 评论0 收藏0
[LintCode/LeetCode] Lowest Common Ancestor of BST/

摘要：递归左右子树，若左右子树都有解，那么返回根节点若仅左子树有解，返回左子树若仅右子树有解，返回右子树若都无解，返回。对于而言，更为简单公共祖先一定是大于等于其中一个结点，小于等于另一个结点。 Problem Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the ...

dinfer 2019-08-14 15:33 评论0 收藏0