Haiyang Yu's Blog
0%

Leetcode 35 Search Insert Position

发表于 更新于 分类于 Valine：
本文字数： 748 阅读时长 ≈ 1 分钟

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

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        while(begin <= end)
        {
            int mid = begin + (end - begin) / 2;
            if(nums[mid] == target)
            {
                return mid;
            }
            else if(nums[mid] > target)
            {
                end = mid - 1;
            }
            else 
            {
                begin = mid + 1;
            }
        }
        return begin;
    }
};

二分查找的变种 注意最后返回的值为begin。 如果查找不到， while结束后必有target在end和begin中间， end在begin左边。所以最后返回begin