Language: Python
Runtime: 28ms
Binary search through the array by utilizing start and end variables to constrain the search area. Because the array is sorted, we are able to tell which "half" of the range that the target should be found in. If the middle of the range is equivalent to the target, return this index. Otherwise, return the start of the range found by contraining the bounds, this is the intended index of the target were it to be in the array.
def searchInsert(self, nums, target):
strt = 0 #start index
end = len(nums) - 1 #end index
mid = 0 #stores the middle of the array
while strt <= end:
mid = strt + (end - strt)//2 #find middle of range of interest
if target == nums[mid]:
return mid
if target < nums[mid]: #target can only be in the first half
end = mid - 1 #adjust range to exclude the second half
elif target > nums[mid]: #target can only be in the second half
strt = mid + 1 #adjust range to exclude first half
return strt #not in array, but start is intended indexComments (0)
