Tìm vị trí đầu và cuối của phần tử trong mảng đã sắp xếp trong Python

Giả sử chúng ta có một mảng số nguyên A đã sắp xếp tăng dần, chúng ta phải tìm vị trí bắt đầu và kết thúc của một giá trị mục tiêu cho trước. Khi mục tiêu không tìm thấy trong mảng, trả về [-1, -1]. Ví dụ, nếu mảng là [2,2,2,3,4,4,4,4,5,5,6], và mục tiêu là 4, đầu ra sẽ là [4,7] (chỉ số 0-based).

Để giải quyết, chúng ta làm theo các bước sau:

• Khởi tạo res := [-1,-1], đặt low := 0, high := độ dài mảng A.
• Khi low < high:
  • mid := low + (high - low)//2.
  • Nếu A[mid] == target:
    • high := mid, res[0] := mid và res[1] := mid.
  • Ngược lại khi A[mid] < target, thì low := mid + 1, ngược lại high := mid.
• Nếu res[0] == -1, trả về res.
• low := res[0] + 1, high := độ dài nums.
• Khi low < high:
  • mid := low + (high - low)//2.
  • Nếu A[mid] == target:
    • low := mid + 1, res[1] := mid.
  • Ngược lại khi A[mid] < target, thì low := mid + 1, ngược lại high := mid.
• Trả về res.

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

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

Đầu ra

[5, 8]