35. Search Insert Position

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

题解：

输入一个有序的数组和一个目标数，查找目标数在数组中出现的位置，如果数组中不存在目标数，则返回该目标数所应插入的数组位置；
数组有序，优先考虑二分查找的方法：
二分查找：https://www.jianshu.com/p/5ca633157c0f
分为两种情况：

1. 数组 nums 中存在目标数 target，则target == nums[mid]：
   直接返回 mid 即可；
2. 数组 nums 中不存在目标数 target，则target != nums[mid]：
   那么目标数可能比二分查找过程中最后一次获得的 nums[mid] 的大或者小；
   target > nums[mid] 时，说明在 mid 的右侧，返回 mid + 1；
   target < nums[mid] 时，说明目标数取代了原来 mid 的位置，返回 mid ；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        int result;
        int mid;
        while (begin <= end) {
            mid = (begin + end) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            else if (target < nums[mid]) {
                result = mid;
                end = mid - 1;
            }
            else if (target > nums[mid]) {
                result = mid + 1;
                begin = mid + 1;
            }
        }
        return result;
    }
};

int main() {
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(3);
    nums.push_back(5);
    nums.push_back(6);
    Solution s;
    printf("%d ", s.searchInsert(nums, 7));
    return 0;
}

结果

4

My Solution(Python)

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

            elif target < nums[mid]:
                if mid == 0 or target > nums[mid - 1]:
                    return mid
                end = mid - 1
       

        # return self.binary_search(0, len(nums) - 1, nums, target)
    # def binary_search(self, begin, end, nums, target):
    #     if begin > end:
    #         return
    #     mid = (begin + end) // 2
    #     if target > nums[mid]:
    #         self.binary_search(mid + 1, end, nums, target)
    #     if target < nums[mid]:
    #         self.binary_search(begin, mid - 1, nums, target)
    #     if target == nums[mid]:
    #         result = mid
        

Reference:

1：

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        size=len(nums)
        if target>nums[size-1]: 
            return size
        if target<=nums[0]: 
            return 0
        return self.bsearch(0,size-1,target,nums)
 
    def bsearch(self,left,right,target,nums):
        p=(left+right)//2
        if target==nums[p]:
            return p
        if (target <nums[p] and target>nums[p-1]):
            return p
        if (target>nums[p] and target<=nums[p+1]):
            return p+1
        if target>nums[p]:
            return self.bsearch(p,right,target,nums)
        if target<nums[p]:
            return self.bsearch(left,p,target,nums)

2：

class Solution(object):
    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