[LintCode/LeetCode] Search Insert Position

cjie 發布于2019-08-14 15:40 / 2354人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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