Leetcode[35] Search Insert Position

jasperyang 發布于2019-08-15 13:51 / 869人閱讀

Leetcode[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.
Example 1:
Input: [1,3,5,6], 5 Output: 2 Example 2:
Input: [1,3,5,6], 2 Output: 1 Example 3:
Input: [1,3,5,6], 7 Output: 4 Example 1:
Input: [1,3,5,6], 0 Output: 0

Binary Search

復雜度
O(lgN)

思路
二分法的模板：

while(left <= right) {
  int mid = (left + right) / 2;
  if(nums[mid] == target) return mid;
  // search in the right part;
  if(nums[mid] < target) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}
return -1;

代碼

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

GPU云服務器云服務器 leetcode_35_SearchIn LeetCode LeetCode_String position()

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68356.html

leetcode35 Search Insert Position

題目要求：在一個有序的數組中，找到一個目標值，返回該值得下標。若沒有找到該值，則返回該值順序插入的下標例如，[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0 public int searchInsert(int[] nums, int target) { int index=0; ...

harriszh 2019-08-14 17:54 評論0 收藏0
【Leetcode刷題】第 35 題：Search Insert Position 搜索插入位置——

摘要：如果目標值不存在于數組中，返回它將會被按順序插入的位置。因此需要關注這些測試用例，在單機上逐個測試成功后再提交。因為題目中只要求返回索引，并不要求插到數組中，所以應該說又簡化了一些，是一道簡單題目。爭取在下一篇給出優化解法。「 Leetcode刷題」系列，僅為刷題過程中對于算法和編程的思考與記錄，如果對你有幫助歡迎點贊收藏。博主也在探索刷題過程中，記錄的一些知識點可能很小白，因此主...

haobowd 2019-07-31 11:17 評論0 收藏0
[Leetcode] Search Insert Position 搜索插入位置

摘要：二分搜索法復雜度時間空間思路這是最典型的二分搜索法了。這題中，我們返回就行了，如果返回，要注意的情況。代碼條件是找到了在左邊在右邊 Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the inde...

JeOam 2019-08-14 12:41 評論0 收藏0
[LintCode/LeetCode] Search Insert Position

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 a...

cjie 2019-08-14 15:40 評論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評論0 收藏0