#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Nov  3 11:46:18 2019

@author: lcui
"""

class Solution:
    # returns leftmost (or rightmost) index at which `target` should be inserted in sorted
    # array `nums` via binary search.
    def find_idx(self, nums, target, left):
        lo = 0
        hi = len(nums)

        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or (left and target == nums[mid]):
                hi = mid
            else:
                lo = mid+1
        return lo

    def searchRange(self, nums, target):
        left_idx = self.find_idx(nums, target, True)

        # assert that `left_idx` is within the array bounds and that `target`
        # is actually in `nums`.
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]

        return [left_idx, self.find_idx(nums, target, False)-1]
"""
data = [2,2]
k = 2
Solution().searchRange(data,k)

data2 = [5,7,7,8,8,10]
k2 = 8
Solution().searchRange(data2,k2)

data3 = [1,2,5,5,5,9]
k3 = 5
Solution().searchRange(data3,k3)

34. Find First and Last Position of Element in Sorted Array
Medium

2169

100

Favorite

Share
Given an array of integers nums 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].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
"""

884c6177864a7ff46024348153a481f607e9a8ae
<mask token>

<mask token>


class Solution:
    <mask token>
    <mask token>


<mask token>

<mask token>


class Solution:

    def find_idx(self, nums, target, left):
        lo = 0
        hi = len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or left and target == nums[mid]:
                hi = mid
            else:
                lo = mid + 1
        return lo
    <mask token>


<mask token>

<mask token>


class Solution:

    def find_idx(self, nums, target, left):
        lo = 0
        hi = len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or left and target == nums[mid]:
                hi = mid
            else:
                lo = mid + 1
        return lo

    def searchRange(self, nums, target):
        left_idx = self.find_idx(nums, target, True)
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]
        return [left_idx, self.find_idx(nums, target, False) - 1]


<mask token>

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Nov  3 11:46:18 2019

@author: lcui
"""

class Solution:
    # returns leftmost (or rightmost) index at which `target` should be inserted in sorted
    # array `nums` via binary search.
    def find_idx(self, nums, target, left):
        lo = 0
        hi = len(nums)

        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > target or (left and target == nums[mid]):
                hi = mid
            else:
                lo = mid+1
        return lo

    def searchRange(self, nums, target):
        left_idx = self.find_idx(nums, target, True)

        # assert that `left_idx` is within the array bounds and that `target`
        # is actually in `nums`.
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]

        return [left_idx, self.find_idx(nums, target, False)-1]
"""
data = [2,2]
k = 2
Solution().searchRange(data,k)

data2 = [5,7,7,8,8,10]
k2 = 8
Solution().searchRange(data2,k2)

data3 = [1,2,5,5,5,9]
k3 = 5
Solution().searchRange(data3,k3)

34. Find First and Last Position of Element in Sorted Array
Medium

2169

100

Favorite

Share
Given an array of integers nums 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].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
"""
