<reponame>Fiona08/leetcode
#35


# Time:  O(logn)
# Space: O(1)


# 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 1:
# Input: [1,3,5,6], 0
# Output: 0


class binarySearchSol():
    def insertPosition(self,nums,target):
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]>=target:
                right=mid-1
            else:
                left=mid+1
        return left

#35


# Time:  O(logn)
# Space: O(1)


# 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 1:
# Input: [1,3,5,6], 0
# Output: 0


class binarySearchSol():
    def insertPosition(self,nums,target):
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]>=target:
                right=mid-1
            else:
                left=mid+1
        return left
#35 # Time:  O(logn) # Space: O(1) # 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 1: # Input: [1,3,5,6], 0 # Output: 0