LeetCode之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].

题目大意：

给定按升序排序的整数数组，找到给定目标值的开始和结束位置。您的算法的运行时复杂度必须按照O（log n）的顺序。如果在数组中找不到目标，则返回[-1，-1]。例如，给定[5，7，7，8，8，10]和目标值8，返回[3，4]。

题目分析：

注意到题目要求时间复杂度为O （log n），可以采用二分法进行目标值搜索。当搜索到目标值时，对中位数进行加一或减一操作确定另一目标数位置。

代码如下：

• Java

        int[] result = {-1,-1};
        int left = 0;
        int right = nums.length-1;
        while (left <= right) {
            int mid = (right+left)/2;
            if (nums[mid] > target)
                right = mid-1;
            else if (nums[mid] < target)
                left = mid+1;
            else {
                result[0] = mid;
                result[1] = mid;

                int i = mid-1;
                while (i>=0 && nums[i] == target) {
                    result[0] = i;
                    --i;
                }

                i = mid+1;
                while (i<nums.length && nums[i] == target) {
                    result[1] = i;
                    ++i;
                }

                break;
            }
        }
        return result;

• Python

        left = 0 
        right = len(nums)-1

        result = [-1,-1]
        while left<=right:
            mid = (left + right) / 2
            if nums[mid] > target:
                right = mid-1
            elif nums[mid] < target:
                left = mid+1
            else:
                result[0] = mid
                result[1] = mid

                i = mid-1
                while i>=0 and nums[i] == target:
                    result[0] = i
                    i-=1

                i = mid+1
                while i<len(nums) and nums[i] == target:
                    result[1] = i
                    i+=1

                break

        return result