class Solution:
def searchInsert(self, nums, target):
"""
If found, return index
If not found, return place to insert.
"""
if len(nums)==0: return 0
left = 0
right = len(nums) - 1
while(left <= right):
# test by subarray length
if left == right: # subarray of lengh 1
if nums[left] == target:
return left
elif nums[left] > target:
return left
else:
return right+1
if (right - left) == 1: # subarray of length 2
if nums[left] >= target:
return left
elif nums[right] == target:
return right
elif nums[right] < target:
return right + 1
elif (nums[left] < target) and (nums[right] > target):
return right
else:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target: # search right array
left = mid + 1
else :
right = mid - 1 # search left array
Iterative version.
One pass except for the last else...
One pass except for the last else...
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.