Python - Search Insert Position-白红宇

Python - Search Insert Position

阅读量：4030 次

发布时间：2019-05-24

本文共 1022 字，大约阅读时间需要 3 分钟。

标签：

2014-09-21 17:50

1027人阅读

(0)

分类：

LeetCode with Python（103）

博客域名：

原题页面：

题目类型：二分查找

难度评价：★★

本文地址：

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

二分查找的一个变种。如果找到了target，就返回下标（正常的二分查找逻辑），否则就返回插入的位置。二分查找容易搞晕的是到底是返回left还是right，注意到left最终一定停在target上，或停在target的“位置”的右边，所以显然找不到target时，应该返回left的下标作为插入位置。

[python]
 class Solution:  
     # @param A, a list of integers  
     # @param target, an integer to be inserted  
     # @return integer  
     def searchInsert(self, A, target):  
         if None == A:  
             return 0  
         len_A = len(A)  
         if target > A[len_A - 1]:  
             return len_A  
         if target < A[0]:  
             return 0  
   
         left = 0  
         right = len_A - 1  
         while left <= right:    # also can be left < right  
             mid = (left + right) / 2  
             if A[mid] < target:  
                 left = mid + 1  
             elif A[mid] > target:  
                 right = mid - 1  
             else:  
                 return mid  
         return left  

你可能感兴趣的文章