Bài 35 Leetcode: Search Insert Position

Đề bài:

Cho một mảng đã được sắp xếp có các số nguyên riêng biệt và một giá trị mục tiêu, trả về chỉ số nếu giá trị mục tiêu được tìm thấy trong mảng. Nếu không tìm thấy, trả về chỉ số mà giá trị mục tiêu sẽ được chèn vào mảng theo thứ tự.

Bạn phải viết một thuật toán với độ phức tạp thời gian O(log n).

Ví dụ 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Ví dụ 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Ví dụ 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Ràng buộc:

• 1 <= độ dài của nums <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums chứa các giá trị riêng biệt đã sắp xếp theo thứ tự tăng dần.
• -10^4 <= target <= 10^4

Giải thích thuật toán bằng C++

class Solution {
 public:
  int searchInsert(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size();

    while (l < r) {
      const int m = (l + r) / 2;
      if (nums[m] == target)
        return m;
      if (nums[m] < target)
        l = m + 1;
      else
        r = m;
    }

    return l;
  }
};

Đoạn code trên là một đoạn code C++ để tìm vị trí chèn của một giá trị `target` trong một mảng đã được sắp xếp `nums`. Dưới đây là giải thích về thuật toán trong đoạn code:

1. Khai báo hai biến `l` và `r`, lần lượt là chỉ số bắt đầu và kết thúc của mảng `nums`.

2. Sử dụng vòng lặp while để thực hiện tìm kiếm trong mảng:

– Tính chỉ số giữa `m` bằng cách lấy trung bình của `l` và `r`: `m = (l + r) / 2`.

– Nếu giá trị `nums[m]` bằng `target`, tức là đã tìm thấy `target`, ta trả về chỉ số `m`.

– Nếu giá trị `nums[m]` nhỏ hơn `target`, tức là `target` nằm bên phải `m`, ta cập nhật `l = m + 1` để tìm kiếm phía bên phải.

– Ngược lại, nếu giá trị `nums[m]` lớn hơn hoặc bằng `target`, tức là `target` nằm bên trái `m` hoặc `target` có thể được chèn vào vị trí `m`, ta cập nhật `r = m` để tìm kiếm phía bên trái hoặc kiểm tra vị trí chèn.

3. Trả về giá trị `l` sau khi kết thúc vòng lặp. Chỉ số `l` sẽ là vị trí chèn của `target` trong mảng `nums`.

Thuật toán trên sử dụng phương pháp tìm kiếm nhị phân để tìm vị trí chèn của `target` trong mảng `nums`. Bằng cách thu hẹp phạm vi tìm kiếm dựa trên giá trị của `nums[m]` so với `target`, thuật toán đảm bảo độ phức tạp thời gian O(log n).

Giải thích thuật toán bằng Java

class Solution {
  public int searchInsert(int[] nums, int target) {
    int l = 0;
    int r = nums.length;

    while (l < r) {
      final int m = (l + r) / 2;
      if (nums[m] == target)
        return m;
      if (nums[m] < target)
        l = m + 1;
      else
        r = m;
    }

    return l;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def searchInsert(self, nums: List[int], target: int) -> int:
    l = 0
    r = len(nums)

    while l < r:
      m = (l + r) // 2
      if nums[m] == target:
        return m
      if nums[m] < target:
        l = m + 1
      else:
        r = m

    return l