ค้นหาตำแหน่งแรกและสุดท้ายขององค์ประกอบในอาร์เรย์ที่เรียงลำดับใน Python

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เริ่มต้น res :=[-1,-1] ตั้งค่าต่ำ :=0, สูง :=ความยาวของอาร์เรย์ A
• ในขณะที่ต่ำ <สูง
  • กลาง :=ต่ำ + (สูง – ต่ำ)/2
  • ถ้า A[กลาง] เป็นเป้าหมาย
    • high :=mid, res[0] :=mid และ res[1] :=mid
  • มิฉะนั้น เมื่อ A[กลาง] <เป้าหมาย จากนั้นต่ำ :=กลาง + 1 มิฉะนั้น สูง :=กลาง
• ถ้า res[0] =-1 ให้คืนค่า res
• ต่ำ :=res[0] + 1, สูง :=ความยาวของ nums
• ในขณะที่ต่ำ <สูง
  • กลาง :=ต่ำ + (สูง – ต่ำ)/2
  • ถ้า A[กลาง] เป็นเป้าหมาย
    • ต่ำ :=กลาง + 1, ความละเอียด[1] :=กลาง
  • มิฉะนั้น เมื่อ A[กลาง] <เป้าหมาย จากนั้นต่ำ :=กลาง + 1 มิฉะนั้น สูง :=กลาง
• ผลตอบแทน

ตัวอย่าง(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]