[leetcode]35. Search Insert Position寻找插入位置

佚名 6年前 (2019-04-12) 随笔 2194人围观抢沙发百度已收录

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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 4:

Input: [1,3,5,6], 0
Output: 0

题意：

给定有序数组和一个target，寻找合适的插入位置。

Solution1: Binary Search

code:

 1 /*
 2 Time: O(log(n))
 3 Space: O(1)
 4 */
 5 class Solution {
 6    public int searchInsert(int[] nums, int target) {
 7         //corner case
 8         if (nums == null || nums.length == 0) {
 9             return 0;
10         }
11         if (target < nums[0]) {   //[1,3,5,6], 0
12             return 0;
13         } else if (target > nums[nums.length - 1]) {  // [1,3,5,6], 7
14             return nums.length;
15         }
16         // binary search
17         int left = 0, right = nums.length - 1;
18         while (left < right) {
19             int mid = left + (right - left) / 2;
20             if (nums[mid] == target) {
21                 return mid;
22             } else if (nums[mid] > target) {
23                 right = mid;
24             } else {
25                 left = mid + 1;
26             }
27         }
28         return left;
29     }
30 }