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 条评论
登录 后参与评论

相关文章

来自专栏kalifaの日々

C++迪杰斯特拉最短路径算法实现

input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

2814
来自专栏aCloudDeveloper

LeetCode:21_Merge Two Sorted Lists | 合并两个排序列表 | Easy

题目:Merge Two Sorted Lists Merge two sorted linked lists and return it as a new l...

1789
来自专栏学习有记

2018 蓝桥杯省赛 B 组模拟赛(五)题目及解析

882
来自专栏计算机视觉与深度学习基础

Leetcode 19 Remove Nth Node From End of List 超简洁代码

Given a linked list, remove the nth node from the end of list and return its he...

1959
来自专栏desperate633

详解排序算法--堆排序选择排序堆排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩...

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

树链剖分详解

前言 树链剖分是什么? 树链剖分,说白了就是一种让你代码不得不强行增加1k的数据结构-dms 个人理解:+1:joy: 有什么用? 证明出题人非常毒瘤 ...

2687
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

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

HDU 3530Subsequence(单调队列)

给出$n$个数,找出最长的区间,使得区间中最大数$-$最小数 $>= m$ 且$<= k$

291
来自专栏程序生活

Leetcode-Easy21. Merge Two Sorted ListsDefinition for singly-linked list.class ListNode:def init(sel

21. Merge Two Sorted Lists 描述: 将两个有序链表进行合并,合并之后的链表也是有序链表 ? 思路: 递归 代码 ...

2523
来自专栏ml

排序

排序法 平均时间 最差情形 稳定度 额外空间 冒泡 O(n2)     O(n2) 稳定 O(1) 交换     O(n2)     O(n2) ...

3065

扫码关注云+社区