# Python, O(logN), with clear explanation

• I used a binary search, by 2 pointers, left and right. In every iteration, I through away half of the nums. So in the first loop I can find the first instance of the smallest larger number. then the rest is pretty straightforward ^8^ (first time writing a post~)

``````class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""

#first use binary search to find the closest larger number in the array
#also we found the first instance of the closest larger number in this way!
n = len(nums)
l , r = 0, n-1
while l<r:
m = int((l+r)/2)
if nums[m]<target: l=m+1
else: r = m

#whether we have found the number?
if nums[l] == target:
return l

#in this case, the target should be added in the end, out of range
if l == n-1 and nums[l]<target:
return l+1

return l
``````

• ``````if nums[l] == target:
return l
``````

Nice Solution! However, these lines are redundant. you can simply remove them.

• ``````class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
return self.bsHelper(nums, target, 0, len(nums) -1)

def bsHelper(self, nums, target, low, high):
if low > high:
return -1
mid = (low + high) /2
if nums[mid] == target:
return mid
elif nums[mid] > target: #Case when target is less than mid
if mid == 0 or nums[mid-1] < target :
return mid
else:
high =  mid -1
return self.bsHelper(nums, target, low, high)
else: #Case when target is greater than mid
if mid == len(nums) - 1 or nums[mid + 1] > target:
return mid + 1
else:
low = mid + 1
return self.bsHelper(nums, target, low, high)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.