Last Position of Target

• Lintcode : 458 / Leetcode : 34
• Level : Easy

Problem

Find the last position of a target number in a sorted array. Return -1 if target does not exist.

Example
Example 1:

Input: nums = [1,2,2,4,5,5], target = 2
Output: 2
Example 2:

Input: nums = [1,2,2,4,5,5], target = 6
Output: -1

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(logn)
space: O(1)

Answer

class Solution {
public:
    int lastPosition(vector<int> &nums, int target) {
        if (nums.size() == 0) return -1;
        int l = 0, r = nums.size() - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] <= target) {
                l = mid;
            }else {
                r = mid;
            }
        }
        if (nums[r] == target) return r;
        if (nums[l] == target) return l;
        return -1;
    }
};

tags: Binary Search

​