leetcode之-题34

题目

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      

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

Dijkstra

迪杰斯特拉算法是典型的求解最短路径的方法。 优点,时间复杂度为O(n2),主要思想就是遍历邻居,找到路径最短的邻居,添加到路径信息里面。再更新这个添加点,是否能...

1767
来自专栏数据结构与算法

BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1

732
来自专栏King_3的技术专栏

leetcode-744-Find Smallest Letter Greater Than Target(改进的二分查找)

2347
来自专栏calmound

Is It A Tree?(并查集)

判断树是否唯一 1.只有一个根节点,(1)在一棵树上一个根节点。1 2 3 2就是两个根节点(1)只有一棵树 2.不成环,入度不大于1 由于数组运行超界导致wa...

3196
来自专栏小樱的经验随笔

Codeforces 719B Anatoly and Cockroaches

B. Anatoly and Cockroaches time limit per test:1 second memory limit per test:25...

2736
来自专栏数据结构与算法

BZOJ4355: Play with sequence(吉司机线段树)

这题最坑的地方在于对于操作1,$C >= 0$, 操作2中需要对0取max,$a[i] >= 0$,这不就是统计最小值出现的次数么??

802
来自专栏我是业余自学C/C++的

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unkonwn to you beforehand. (i.e...

875
来自专栏Bingo的深度学习杂货店

Q35 Search Insert Position

Given a sorted array and a target value, return the index if the target is found...

2637
来自专栏数据结构与算法

洛谷P3953 逛公园(dp 拓扑排序)

首先不难想到一个思路,\(f[i][j]\)表示到第\(i\)个节点,与最短路之差长度为\(j\)的路径的方案数

653
来自专栏wym

Codeforces Round #483 (Div. 2) D. XOR-pyramid

For an array bb of length mm we define the function ff as

861

扫码关注云+社区