[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 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

tag: binary search

常规的二分查找,如果没有找到(i == j),则判断A[i]与target的大小,分情况插入i位或i+1位。如果i==n,要单独判断。

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int i = 0;
        int j = n;
        while(i < j){
            int mid = (i + j) / 2;
            if(A[mid] == target){
                return mid;
            }
            if(A[mid] < target){
                i = mid + 1;
            }
            else{
                j = mid;
            }
        }
        if(i == n){
            return n;
        }
        if(A[i] < target){
            return i + 1;
        }
        else{
            return i;
        }
    }
};

Untitled

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.