Question: http://oj.leetcode.com/problems/search-insert-position/
Question Name: Search Insert Position
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution: # @param A, a list of integers # @param target, an integer to be inserted # @return integer def searchInsert(self, A, target): ''' A variant of the binary search algorithm If target is in A, return the position of its first occurrence. Otherwise, rethurn the position of the first element, which is larger than target. ''' begin = 0 end = len(A) - 1 insertPos = 0 while begin <= end: mid = (begin + end) // 2 if A[mid] == target: # Target found return mid elif A[mid] > target: end = mid - 1 insertPos = mid else: begin = mid + 1 insertPos = mid + 1 return insertPos |