[300 Bài Code Thiếu Nhi] Binary Search

Mô tả bài toán

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

Giải pháp

Binary Search (Tìm kiếm nhị phân)  là một thuật toán hiệu quả để tìm kiếm một giá trị mục tiêu cụ thể trong một mảng đã được sắp xếp. Ý tưởng của thuật toán là liên tục chia đôi khoảng không gian tìm kiếm cho đến khi tìm thấy giá trị đích hoặc không. Bằng cách sử dụng phương pháp này, chúng ta có thể nhanh chóng loại bỏ một nửa không gian tìm kiếm còn lại ở mỗi lần lặp lại, dẫn đến độ phức tạp về thời gian là O(log n).

Thuật toán bắt đầu bằng cách so sánh giá trị đích với phần tử ở giữa của mảng đã sắp xếp. Nếu mục tiêu bằng với phần tử ở giữa, chúng ta trả về chỉ mục của phần tử ở giữa. Nếu mục tiêu nhỏ hơn phần tử ở giữa, chúng ta lặp lại tìm kiếm ở nửa bên trái của mảng. Nếu mục tiêu lớn hơn phần tử ở giữa, chúng ta lặp lại tìm kiếm ở nửa bên phải của mảng. Chúng ta tiếp tục quá trình này cho đến khi tìm thấy mục tiêu hoặc đến hết không gian tìm kiếm.

Khởi tạo các con trỏ trái (left) và phải (right) tương ứng đến đầu và cuối mảng.

Trong khi con trỏ bên trái nhỏ hơn hoặc bằng con trỏ bên phải:

1. Tính chỉ số ở giữa (middle) là trung bình của các con trỏ bên trái và bên phải.
2. Nếu phần tử ở giữa bằng với mục tiêu, hãy trả về chỉ mục của phần tử ở giữa.
3. Nếu phần tử ở giữa nhỏ hơn mục tiêu, hãy cập nhật con trỏ bên trái thành middle+ 1.
4. Nếu phần tử ở giữa lớn hơn mục tiêu, hãy cập nhật con trỏ bên phải thành middle – 1.

Nếu không tìm thấy mục tiêu, trả về -1.

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1

        while left <= right:
            middle = (left + right) // 2

            if nums[middle] == target:
                return middle
            elif nums[middle] < target:
                left = middle + 1
            else:
                right = middle - 1
        
        return -1

Trên đây là hiểu biết và cách giải của mình về binary search. Nếu thấy hay hãy để lại 1 like và comment ý kiến của bạn.

You need to login in order to like this post: click here