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

Giả sử chúng ta có một mảng các số nguyên A. Nó được sắp xếp theo thứ tự 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ị đích cho trước. Khi mục tiêu không được tìm thấy trong mảng, trả về [-1, -1]. Vì vậy, nếu mảng giống như [2,2,2,3,4,4,4,4,5,5,6] và mục tiêu là 4, thì đầu ra sẽ là [4,7]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Ban đầu res:=[-1, -1], đặt low:=0, high:=length của mảng A
• trong khi thấp
• giữa:=low + (cao - thấp) / 2
• nếu A [giữa] là mục tiêu, thì
  • high:=mid, res [0]:=mid và res [1]:=mid
• ngược lại khi A [mid]

Ví dụ (Python)

Hãy cùng chúng tôi xem cách 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]