[Leetcode][python/java]Search for a Range/有序数组中的单一元素

超、凢脫俗 2022-06-08 02:39 145阅读 0赞

## 题目大意 ##

查找升序数组第一次出现target数字的范围，返回索引号。题目要求的时间复杂度是O(log n)。

## 解题思路 ##

二分查找变种，二分法时间复杂度就是O(log n)

## 代码 ##

### Java: 重复数组中的二分法找最左 ###

[https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3.md\#%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE][https_github.com_CyC2018_Interview-Notebook_blob_master_notes_Leetcode_20_E9_A2_98_E8_A7_A3.md_E4_BA_8C_E5_88_86_E6_9F_A5_E6_89_BE]

public int[] searchRange(int[] nums, int target) {
        int first = binarySearch(nums, target);
        int last = binarySearch(nums, target + 1) - 1;
        if (first == nums.length || nums[first] != target)
            return new int[]{-1, -1};
        else
            return new int[]{first, Math.max(first, last)};
    }
    
    private int binarySearch(int[] nums, int target) {
        int l = 0, h = nums.length; // 注意 h 的初始值
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] >= target)
                h = m;
            else
                l = m + 1;
        }
        return l;
    }

### Python：二分法找到后直接往前后遍历 ###

class Solution:
        # @param A, a list of integers
        # @param target, an integer to be searched
        # @return a list of length 2, [index1, index2]
        def searchRange(self, A, target):
            left = 0; right = len(A) - 1
            while left <= right:
                mid = (left + right) / 2
                if A[mid] > target:
                    right = mid - 1
                elif A[mid] < target:
                    left = mid + 1
                else:
                    list = [0, 0]
                    if A[left] == target: list[0] = left
                    if A[right] == target: list[1] = right
                    for i in range(mid, right+1):
                        if A[i] != target: list[1] = i - 1; break
                    for i in range(mid, left-1, -1):
                        if A[i] != target: list[0] = i + 1; break
                    return list
            return [-1, -1]

## 总结 ##

[https_github.com_CyC2018_Interview-Notebook_blob_master_notes_Leetcode_20_E9_A2_98_E8_A7_A3.md_E4_BA_8C_E5_88_86_E6_9F_A5_E6_89_BE]: https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3.md#%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE