kniost

谁怕，一蓑烟雨任平生

0%

LeetCode 35. Search Insert Position

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟
LeetCode 35. Search Insert Position

35. Search Insert Position

Difficulty:: Easy

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:

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

Example 2:

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

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

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

Solution

Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
      public int searchInsert(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                  return 0;
           }
            if (nums[0] >= target) {
                  return 0;
           }
            int start = 0, end = nums.length - 1;
            while (start + 1 < end) {
                  int mid = start + (end - start) / 2;
                  if (target == nums[mid]) {
                        return mid;
                 } else if (target < nums[mid]) {
                        end = mid;
                 } else {
                        start = mid;
                 }
           }
            if (nums[end] >= target) {
                  return end;
           } else {
                  return nums.length;
           }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums[0] > target) {
            return 0;
        }
        if (nums[nums.length - 1] < target) {
            return nums.length;
        }
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (nums[start] >= target) {
            return start;
        }
        if (nums[end] >= target) {
            return end;
        }
        return -1;
    }
}