Leetcode-34Search for a Range

34. Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

题解：

输入一个包含重复元素的有序的数组 nums 和目标数target，输出目标数在nums 上的对应区间 result = [getBegin, getEnd]；如果 target 不在 nums 中，输出 result = [-1, -1]；
输入的是有序数组，优先考虑二分查找：https://www.jianshu.com/p/5ca633157c0f
查找 target 在无重复 nums 中的对应位置：https://www.jianshu.com/p/37ae38bdd3a5
这道题我们查找 target 在nums 中的对应位置是不够的，需要增加额外的条件来获取target 在nums 中的区间左端点的对应位置和区间右端点的对应位置；
在满足 target == nums[mid] 的这个大前提下：
如果 nums[mid] 是区间左端点，有两种情况：

1. nums[mid] 是数组 nums 的第一个元素（mid == 0）；
2. nums[mid] 比它左边的元素值大（nums[mid] > nums[mid - 1]）；

如果 nums[mid] 是区间右端点，有两种情况：

1. nums[mid] 是数组 nums 的最后一个元素（mid == nums.size() - 1）；
2. nums[mid] 比它右边的元素值小（nums[mid] < nums[mid - 1]）；

那如果 nums[mid] 既不是区间左端点，也不是区间右端点呢要怎么处理呢？
我们可以用两个函数分别用于获取左端点和获取右端点；

1. 在获取左端点的函数 getBegin() 中：
   在满足 target == nums[mid] 的这个大前提下：
   如果 nums[mid] 不是区间左端点：
   说明左端点在 nums[mid] 的左侧，所以我们只需要取 nums[mid] 的前半段（ end = mid - 1），然后继续查找左端点位置即可；
2. 在获取左端点的函数 getBegin() 中：
   在满足 target == nums[mid] 的这个大前提下：
   如果 nums[mid] 不是区间右端点：
   说明右端点在 nums[mid] 的右侧，所以我们只需要取 nums[mid] 的后半段（ begin = mid + 1），然后继续查找右端点位置即可；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int> &nums, int target) {
        vector<int> result;
        //int begin = 0;
        //int end = nums.size() - 1;
        result.push_back(getBegin(nums, target));
        result.push_back(getEnd(nums, target));
        return result;
    }
private:
    int getBegin(vector<int> &nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        while (begin <= end) {
            int mid = (begin + end) / 2;
            if (target < nums[mid]) {
                end = mid - 1;
            }
            else if (target > nums[mid]) {
                begin = mid + 1;
            }
            else if (target == nums[mid]) {
                if (mid == 0 || target > nums[mid - 1]) {
                    return mid;
                }
                end = mid - 1;
            }
        }
        return -1;
    }
    int getEnd(vector<int> &nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        while (begin <= end) {
            int mid = (begin + end) / 2;
            if (target < nums[mid]) {
                end = mid - 1;
            }
            else if (target > nums[mid]) {
                begin = mid + 1;
            }
            else if (target == nums[mid]) {
                if (mid == nums.size() - 1 || target < nums[mid + 1]) {
                    return mid;
            }
                begin = mid + 1;
            }
        }
        return -1;
    }
};

int main() {
    vector<int> nums;
    nums.push_back(5);
    nums.push_back(7);
    nums.push_back(7);
    nums.push_back(8);
    nums.push_back(8);
    nums.push_back(10);
    Solution s;
    vector<int> result;
    result = s.searchRange(nums, 8);
    for (int i = 0; i < result.size(); i++) {
        printf("%d ", result[i]);
    }
    return 0;
}

结果

3 4

My Solution(Python)

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # begin, end, left, right = 0, len(nums) - 1, -1, -1
        left = self.binary_get_left(0, len(nums) - 1, -1, nums, target)
        right = self.binary_get_right(0, len(nums) - 1, -1, nums, target)
        return [left, right]
    
    def binary_get_left(self, begin, end, left, nums, target):
        while begin <= end:
            mid = (begin + end) // 2
            if nums[mid] == target:
                if mid == 0 or nums[mid - 1] != target:
                    left = mid
                #     begin = mid + 1
                # else:
                end = mid - 1
                # if mid == len(nums) - 1 or nums[mid + 1] != target:
                #     right = mid
                    # end = mid - 1
            elif nums[mid] < target:
                begin = mid + 1
            else:
                end = mid - 1
        return left
    def binary_get_right(self, begin, end, right, nums, target):
        while begin <= end:
            mid = (begin + end) // 2
            if nums[mid] == target:
                # if mid == 0 or nums[mid - 1] != target:
                #     left = mid
                #     begin = mid + 1
                # else:
                #     end = mid - 1
                if mid == len(nums) - 1 or nums[mid + 1] != target:
                    right = mid
                #     end = mid - 1
                # else:
                begin = mid + 1
            elif nums[mid] < target:
                begin = mid + 1
            else:
                end = mid - 1
        return right

Reference:

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        start = self.firstGreaterEqaul(nums, target)
        if start==len(nums) or nums[start]!=target:
            return [-1, -1]
        return [start, self.firstGreaterEqaul(nums, target+1)-1]
    def firstGreaterEqaul(self, nums, target):
        lo, hi = 0, len(nums)
        while lo<hi:
            mid = (hi+lo)//2
            if nums[mid]<target:
                lo = mid + 1
            else:
                hi = mid
        return lo