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.

Example 1:


Input: [1,3,5,6], 5
Output: 2


Example 2:


Input: [1,3,5,6], 2
Output: 1


Example 3:


Input: [1,3,5,6], 7
Output: 4


Example 4:


Input: [1,3,5,6], 0
Output: 0

Difficulty: introductory

Starter code:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        

Solutions:
class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
 
         num=[i for i in nums if i<target]
         return len(num)

class Solution:
     '''Complexity O(log(n))'''
     def searchInsert(self, nums, target):
         low = 0
         high = len(nums) - 1
 
         while low <= high:
             mid = (low + high) // 2
 
             if nums[mid] == target:
                 return mid
             elif nums[mid] < target:
                 low = mid + 1
             else:
                 high = mid - 1
 
         return low

class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         l, r = 0, len(nums)-1
 
         while l <= r:
             m = (l + r) // 2
             if target <= nums[m]:
                 r = m - 1            
             elif target > nums[m]:
                 l = m + 1                
         return l 
                 
           
                 


class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         if nums[-1]<target:
             return len(nums)
         index=0
         while(nums[index]<target):
             index+=1
         return index

class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         start=0
         end=len(nums)-1
         
         while(start<=end):
             mid=(start+end)//2
             if nums[mid]==target:
                 return mid
             elif nums[mid]<target:
                 start=mid+1
             else:
                 end=mid-1
         return end+1

class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         left, right = 0, len(nums)-1
         while left <= right:
             mid = (left+right) // 2
             if nums[mid] == target:
                 return mid
             elif nums[mid] > target:
                 right = mid-1
             else:
                 left = mid+1
         return left


class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         if nums is None:
             return None
         if nums == []:
             return 0
         start, end = 0, len(nums) - 1
         while(start + 1 < end):
             mid = start + (end - start) // 2
             if(nums[mid] > target):
                 end = mid
             else:
                 start = mid
         if(nums[start] >= target):
             return start
         elif(nums[end] >= target):
             return end
         else:
             return end + 1

class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         for i,num in enumerate(nums):
             if num >= target:
                 return i
         return len(nums)

class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         left, right = 0, len(nums) - 1
         while left <= right:
             mid = left + (right - left) // 2
             if nums[mid] >= target:
                 right = mid - 1
             else:
                 left = mid + 1
 
         return left
         


class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         return len([x for x in nums if x < target])


class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         i = 0
         n = len(nums)
         
         if n == 0:
             return 0 if nums[0] >= target else 1
         else:
             if nums[n-1] < target:
                 return n
             else:           
                 while i < n:
                     if nums[i] >= target:
                         return i
                     else:
                         i += 1


class Solution:
     def searchInsert(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         if target in nums:
             return nums.index(target)
         else:
             index = 0
             target -= 1
             while target > 0:
                 if target in nums:
                     return nums.index(target)+1
                 else:
                     target -= 1
             return index