題目：

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

?

代碼：oj測(cè)試通過?Runtime:?52 ms

1 class Solution: 2 # @param A, a list of integers 3 # @param target, an integer to be inserted 4 # @return integer 5 def search(self, A, start, end, target): 6 # search stop case I 7 if start == end: 8 if start == 0: 9 return [ 0,1 ][ A[0]<target ] 10 if A[start] == target: 11 return start 12 else: 13 return [start,start+1][A[start]<target] 14 # search stop case II 15 if start+1 == end: 16 if A[start] >= target: 17 return start 18 elif A[start] < target and A[end] >= target : 19 return end 20 else: 21 return end+1 22 23 mid = (start+end)/2 24 # search stop case III 25 if A[mid] == target: 26 return mid 27 if A[mid] > target: 28 return self.search(A, start, mid-1, target) 29 if A[mid] < target: 30 return self.search(A, mid+1, end, target) 31 32 def searchInsert(self, A, target): 33 # zero length case 34 if len(A) == 0: 35 return 0 36 # binary search 37 start = 0 38 end = len(A)-1 39 return self.search(A, start, end, target)

思路：

二分查找經(jīng)典題。

采用迭代方式時(shí)：

1. 考慮start==end的情況（一個(gè)元素）和start+1==end的情況（兩個(gè)元素），作為迭代終止的兩種case。

2. 當(dāng)元素?cái)?shù)量大于3時(shí)作為一般的case處理，二分查找。

3. 根據(jù)題意要求進(jìn)行判斷條件。

4. 第一次提交沒有AC ，原因是在處理start==end的case時(shí)候，竟然只考慮了0和len(A)的邊界情況，沒有考慮一般情況，陷入了思維的陷阱。

?

后面又寫了一版非遞歸的代碼：oj測(cè)試通過?Runtime:?63 ms

1 class Solution: 2 # @param A, a list of integers 3 # @param target, an integer to be inserted 4 # @return integer 5 def searchInsert(self, A, target): 6 # zero length case 7 if len(A) == 0 : 8 return 0 9 # binary search 10 start = 0 11 end = len(A)-1 12 while start <= end : 13 if start == end: 14 if start == 0: 15 return [0,1][A[0]<target] 16 if A[start] == target: 17 return start 18 else: 19 return [start,start+1][A[start]<target] 20 if start+1 == end: 21 if A[start] >= target: 22 return start 23 elif A[start] < target and A[end] >= target: 24 return end 25 else: 26 return end+1 27 mid = (start+end)/2 28 if A[mid] == target: 29 return mid 30 elif A[mid] > target: 31 end = mid - 1 32 else: 33 start = mid + 1

思路跟非遞歸差不太多。

個(gè)人感覺判斷stop case的代碼雖然邏輯上比較清晰（剩一個(gè)元素或者兩個(gè)元素或者直接找到了target），但是并不是很簡(jiǎn)潔。后續(xù)再不斷改進(jìn)。

轉(zhuǎn)載于:https://www.cnblogs.com/xbf9xbf/p/4245711.html

總結(jié)

以上是生活随笔為你收集整理的leetcode 【 Search Insert Position 】python 实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。