สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums พวกมันถูกเรียงลำดับจากน้อยไปมาก นอกจากนี้เรายังมีเป้าหมายตัวเลขอีกตัวหนึ่ง เราต้องหาดัชนีที่ควรแทรกเป้าหมายเพื่อเก็บ nums ไว้ หากเป้าหมายมีอยู่แล้วใน nums ให้ส่งคืนดัชนีที่ใหญ่ที่สุดที่สามารถแทรกเป้าหมายได้ เราต้องแก้ปัญหานี้โดยไม่ต้องใช้ฟังก์ชั่นห้องสมุดและแก้ไขในเวลา O(log n)
ดังนั้น หากอินพุตเท่ากับ nums =[1,5,6,6,8,9] เป้าหมาย =6 ผลลัพธ์จะเป็น 4 เนื่องจาก 6 มีอยู่แล้ว ดังนั้นการใส่เข้าไป ดัชนีที่ใหญ่ที่สุดคือ 4 ดังนั้นอาร์เรย์จะเป็นเช่น [1,5,6,6,6,8,9]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ซ้าย :=0
- ขวา :=
- ขนาดของตัวเลข - 1
- ตอบ :=0
- ขณะซ้าย <=ขวา ทำ
- กลาง :=ชั้นของ (ซ้าย + ขวา) / 2
- ถ้าเป้าหมาย>=nums[mid] แล้ว
- ans :=กลาง + 1
- ซ้าย :=กลาง + 1
- มิฉะนั้น
- ขวา :=กลาง - 1
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(nums, target): left, right = 0, len(nums) - 1 ans = 0 while left <= right: mid = (left + right) // 2 if target >= nums[mid]: ans = mid + 1 left = mid + 1 else: right = mid - 1 return ans nums = [1,5,6,6,8,9] target = 6 print(solve(nums, target))
อินพุต
[1,5,6,6,8,9], 6
ผลลัพธ์
4
