Find First and Last Position of Element in Sorted Array ใน Python

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม A เรียงลำดับจากน้อยไปมาก เราต้องหาตำแหน่งเริ่มต้นและสิ้นสุดของค่า target ที่กำหนด ถ้าไม่พบ target คืน [-1, -1] ตัวอย่าง อาร์เรย์ [2,2,2,3,4,4,4,4,5,5,6] target = 4 ผลลัพธ์ [4,7] (0-indexed)

ขั้นตอนการทำงาน (Binary Search สองครั้ง)

1. ตั้งค่า res := [-1,-1], low := 0, high := len(A)
2. Binary search หาตำแหน่งแรก (leftmost):
   • mid := low + (high - low) // 2
   • ถ้า A[mid] == target: high := mid, res[0] := mid, res[1] := mid
   • ถ้า A[mid] < target: low := mid + 1 มิฉะนั้น high := mid
3. ถ้า res[0] == -1 คืน res
4. Binary search หาตำแหน่งสุดท้าย (rightmost):
   • low := res[0] + 1, high := len(nums)
   • mid := low + (high - low) // 2
   • ถ้า A[mid] == target: low := mid + 1, res[1] := mid
   • ถ้า A[mid] < target: low := mid + 1 มิฉะนั้น high := mid
5. คืนค่า res

ตัวอย่างโค้ด (Python)

class Solution(object):
    def searchRange(self, nums, target):
        res = [-1, -1]
        low = 0
        high = len(nums)
        while low < high:
            mid = int(low + (high - low) // 2)
            if nums[mid] == target:
                high = mid
                res[0] = mid
                res[1] = mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid
        if res[0] == -1:
            return res
        low = res[0] + 1
        high = len(nums)
        while low < high:
            mid = int(low + (high - low) // 2)
            if nums[mid] == target:
                low = mid + 1
                res[1] = mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid
        return res

ob1 = Solution()
print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))

อินพุต

[2,2,2,3,4,4,4,4,5,5,6] 4

เอาต์พุต

[5, 8]