查找

题目：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

给定一个排序好的数组，对其进行查找，这里我使用了两种方法，第一种是暴力查找，对数组进行顺序遍历，时间复杂度为O(n)，第二种是二分查找，时间复杂度是O（lgn）

• 暴力查找

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

• 二分查找

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

二分查找的思想是每次都从数组的中间开始查找，若小于则去左半部分