# https://leetcode.com/problems/search-insert-position/
# 35. Search Insert Position

# History:
# Google
# 1.
# Mar 28, 2019
# 2.
# Feb 19, 2020
# 3.
# Apr 11, 2021

# 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


class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums)

        while l < r:
            m = (r - l) / 2 + l

            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m
            else:
                l = m + 1

        return l
