Chương trình tìm chỉ mục, nơi chúng ta có thể chèn phần tử để giữ danh sách được sắp xếp bằng Python

Giả sử chúng ta có một danh sách các số được gọi là nums, chúng được sắp xếp theo thứ tự tăng dần, chúng ta cũng có một mục tiêu số khác, chúng ta phải tìm chỉ mục mà mục tiêu sẽ được chèn vào để giữ cho số được sắp xếp. Nếu mục tiêu đã có trong nums, thì trả về chỉ mục lớn nhất mà mục tiêu có thể được chèn vào. Chúng ta phải giải quyết vấn đề này mà không sử dụng các hàm thư viện và giải quyết nó trong thời gian O (log n).

Vì vậy, nếu đầu vào giống như nums =[1,5,6,6,8,9] target =6, thì đầu ra sẽ là 4, bởi vì 6 đã ở đó, vì vậy để chèn nó, chỉ số lớn nhất có thể là 4 , vì vậy mảng sẽ có dạng [1,5,6,6,6,8,9].

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

• trái:=0
• đúng:=
• kích thước của nums - 1
• ans:=0
• khi left <=right, thực hiện
  • giữa:=tầng của (trái + phải) / 2
  • nếu target> =nums [mid], thì
    • ans:=mid + 1
    • left:=mid + 1
  • nếu không,
    • right:=mid - 1
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

[1,5,6,6,8,9], 6

Đầu ra

4