Leetcode 35. Search Insert Position

給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。

Python

方法 : BinarySearch 二分搜尋法

首先，設置左指針 left 和右指針 right，分別指向數組的開頭和結尾。然後，計算出中間的索引 mid，並比較目標值 target 與數組中索引為 mid 的元素的大小。

如果 target 等於數組中索引為 mid 的元素，則找到了目標值，返回 mid。
如果 target 小於數組中索引為 mid 的元素，則說明目標值在數組的左半部分，將 right 設置為 mid-1。
如果 target 大於數組中索引為 mid 的元素，則說明目標值在數組的右半部分，將 left 設置為 mid+1。

class Solution:
    def searchInsert(self, nums, target):
        left = 0; right = len(nums) - 1
        while left <= right:
            mid = ( left + right ) // 2
            if nums[mid] < target:   #當target大於中位數，捨棄左半
                left = mid + 1
            elif nums[mid] > target: #當target小於中位數，捨棄右半
                right = mid - 1
            else:
                return mid      #不斷更新right或left值，直到找到新的mid值
        return left

C++

方法 : BinarySearch 二分搜尋法

nums[mid] < target 左邊界變成mid+1

nums[mid] > target 左邊界變成mid

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

Python

C++

相關