leetcode之-题34

GavinZhou

发布于 2018-01-02 15:54:32

4750

发布于 2018-01-02 15:54:32

题目

Search for a Range Given a sorted array of integers, 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)，已经想到了需要使用二分查找，二分查找很简单，关键是这个题目要我们找到target的区间其实很简单，分成两步就好了，第一次尽量向左走，第二次尽量向右走，获得左边和右边的位置，返回即可

(1)寻找最左的index: 找到相等时，high=mid，让它一直向左走
(2)寻找最右的index: 找到相等时，low=mid，让它一直向右走

代码

#!/usr/bin/python
# -*- coding:utf-8 -*-

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return [-1, -1]
        start_index = self.lsearch(nums, target)
        end_index = self.rsearch(nums, target)
        return [start_index, end_index]

    def rsearch(self, nums, target):
        # 二分查找，相等时候一直向右
        low = 0
        high = len(nums) - 1
        while low < high - 1:
            mid_index = (low + high) // 2
            if nums[mid_index] > target:
                high = mid_index - 1
            elif nums[mid_index] < target:
                low = mid_index + 1
            else:
                low = mid_index
        if nums[high] == target:
            return high
        elif nums[low] == target:
            return low
        else:
            return -1

    def lsearch(self, nums, target):
        # 二分查找，一直向左走
        low = 0
        high = len(nums) - 1
        while low < high - 1:
            mid_index = (low + high) // 2
            if nums[mid_index] > target:
                high = mid_index - 1
            elif nums[mid_index] < target:
                low = mid_index + 1
            else:
                high = mid_index
        if nums[low] == target:
            return low
        elif nums[high] == target:
            return high
        else:
            return -1


if __name__ == '__main__':

    a = Solution()
    st = a.searchRange([1,8,8,8,8,9,9,10,10,10,11], 8)
    print st

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-05-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

position