35. Search Insert Position

Leetcode Array Binary Search

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

这道题比较简单，就是二分查找(binary search)。思路就是每次取中间，如果等于目标即返回，否则根据大小关系切去一半。因此算法复杂度是$O(\log n)$，空间复杂度$O(1)$。

注意以上实现方式有一个好处，就是当循环结束时，如果没有找到目标元素，那么first一定停在恰好比目标大的index上，right一定停在恰好比目标小的index上。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        first = 0
        last = len(nums) - 1
        found = False

        while first <= last and not found:

            mid = (first + last) //2
            if nums[mid] == target:
                found = True
                return mid
            elif nums[mid] > target:
                last = mid - 1
            else:
                first = mid + 1

        return first