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.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

分析

二分法，和Binary-Search标签下的First Bad Version是一样的，其实写几道这样的题目就会发现，在脑袋里构建边界情况总是比不上写上几个例子，或者直接写代码来得清晰

解决方案1(C++)

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

相关问题

(E) First Bad Version

题目来源