在Python中查找插入元素以保持列表排序的索引的程序

假设我们有一个名为nums的按升序排列的数字列表，我们还有另一个数字目标target，我们必须找到插入目标的索引以保持nums排序。如果目标已经存在于nums中，则返回可插入目标的最大索引。我们必须不使用库函数解决此问题，并在O(log n)时间内解决。

因此，如果输入是nums = [1,5,6,6,8,9] target = 6，则输出将为4，因为6已经存在，因此将其插入的最大可能索引为4，因此数组将为[1,5,6,6,6,8,9]。

为了解决这个问题，我们将遵循以下步骤 −

left := 0
right :=
size of nums – 1
ans := 0
while left <= right, do
- mid := floor of (left + right) / 2
- if target >= nums[mid], then
  - ans := mid + 1
  - left := mid + 1
- otherwise,
  - right := mid – 1
return ans

示例

让我们看一下以下实现，以更好地理解−

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