Leetcode[35] Search Insert Position

jasperyang 发布于2019-08-15 13:51 / 863人阅读

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()

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

转载请注明本文地址：https://www.ucloud.cn/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