[LintCode/LeetCode] Search Insert Position

cjie 發(fā)布于2019-08-14 15:40 / 2356人閱讀

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;
    }
}

云服務(wù)器 GPU云服務(wù)器 position() position insert position:absolute

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65937.html

相關(guān)文章

[LintCode/LeetCode] Implement Trie

摘要：首先，我們應(yīng)該了解字典樹的性質(zhì)和結(jié)構(gòu)，就會很容易實現(xiàn)要求的三個相似的功能插入，查找，前綴查找。既然叫做字典樹，它一定具有順序存放個字母的性質(zhì)。所以，在字典樹的里面，添加，和三個參數(shù)。 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 [左右邊界法/一次循環(huán)

摘要：首先，建立二元結(jié)果數(shù)組，起點，終點。二分法求左邊界當中點小于，移向中點，否則移向中點先判斷起點，再判斷終點是否等于，如果是，賦值給。 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

摘要：找中點若起點小于中點，說明左半段沒有旋轉(zhuǎn)，否則說明右半段沒有旋轉(zhuǎn)。在左右半段分別進行二分法的操作。只判斷有無，就容易了。還是用二分法優(yōu)化 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

摘要：構(gòu)造數(shù)組，是的，是的，是將位的轉(zhuǎn)換成位的需要的步數(shù)。初始化和為到它們各自的距離，然后兩次循環(huán)和即可。 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/

摘要：遞歸左右子樹，若左右子樹都有解，那么返回根節(jié)點若僅左子樹有解，返回左子樹若僅右子樹有解，返回右子樹若都無解，返回。對于而言，更為簡單公共祖先一定是大于等于其中一個結(jié)點，小于等于另一個結(jié)點。 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