[LintCode/LeetCode] Search Insert Position

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

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

標(biāo)準(zhǔn)二分法題目。

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云服務(wù)器云服務(wù)器 position() position insert position:absolute

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65937.html

相關(guān)文章

[LintCode/LeetCode] Implement Trie

摘要：首先，我們應(yīng)該了解字典樹(shù)的性質(zhì)和結(jié)構(gòu)，就會(huì)很容易實(shí)現(xiàn)要求的三個(gè)相似的功能插入，查找，前綴查找。既然叫做字典樹(shù)，它一定具有順序存放個(gè)字母的性質(zhì)。所以，在字典樹(shù)的里面，添加，和三個(gè)參數(shù)。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

付永剛 2019-08-14 15:23 評(píng)論0 收藏0
[LintCode/LeetCode] Search for a Range [左右邊界法/一次循環(huán)

摘要：首先，建立二元結(jié)果數(shù)組，起點(diǎn)，終點(diǎn)。二分法求左邊界當(dāng)中點(diǎn)小于，移向中點(diǎn)，否則移向中點(diǎn)先判斷起點(diǎn)，再判斷終點(diǎn)是否等于，如果是，賦值給。 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 評(píng)論0 收藏0
[LintCode/LeetCode] Search in Rotated Sorted Arra

摘要：找中點(diǎn)若起點(diǎn)小于中點(diǎn)，說(shuō)明左半段沒(méi)有旋轉(zhuǎn)，否則說(shuō)明右半段沒(méi)有旋轉(zhuǎn)。在左右半段分別進(jìn)行二分法的操作。只判斷有無(wú)，就容易了。還是用二分法優(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 評(píng)論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 評(píng)論0 收藏0
[LintCode/LeetCode] Lowest Common Ancestor of BST/

摘要：遞歸左右子樹(shù)，若左右子樹(shù)都有解，那么返回根節(jié)點(diǎn)若僅左子樹(shù)有解，返回左子樹(shù)若僅右子樹(shù)有解，返回右子樹(shù)若都無(wú)解，返回。對(duì)于而言，更為簡(jiǎn)單公共祖先一定是大于等于其中一個(gè)結(jié)點(diǎn)，小于等于另一個(gè)結(jié)點(diǎn)。 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 評(píng)論0 收藏0