Tìm kiếm một số trong một danh sách được sắp xếp với thuật toán tìm kiếm nhị phân

Bài tập giải thuật với Python

0.0 (0 đánh giá)
Tạo bởi Kteam Cập nhật lần cuối 23:50 04-05-2023 1.636 lượt xem 0 bình luận
Tác giả/Dịch giả: K9
Học nhanh

Danh sách bài học

Tìm kiếm một số trong một danh sách được sắp xếp với thuật toán tìm kiếm nhị phân

Yêu cầu bài toán

Viết một chương trình Python để tìm kiếm một số trong một danh sách được sắp xếp. Sử dụng thuật toán tìm kiếm nhị phân để giảm thiểu số lần so sánh cần thiết.


Thuật toán tìm kiếm nhị phân

Thuật toán tìm kiếm nhị phân là một thuật toán tìm kiếm trong một danh sách được sắp xếp. Vì vậy, yêu cầu để áp dụng thuật toán tìm kiếm nhị phân là danh sách cần được sắp xếp theo thứ tự tăng hoặc giảm dần.

Thuật toán này sử dụng kỹ thuật chia để trị để tìm kiếm một phần tử trong danh sách.

Nguyên lý hoạt động bằng cách so sánh giá trị của phần tử ở giữa của danh sách với giá trị cần tìm dẫn đến 1 trong 3 trường hợp:

  • Nếu giá trị của phần tử ở giữa = giá trị cần tìm, thuật toán trả về chỉ số của phần tử này.
  • Nếu giá trị của phần tử ở giữa > giá trị cần tìm, thuật toán tìm kiếm trong nửa đầu tiên của danh sách (bên trái phần tử ở giữa)
  • Nếu giá trị của phần tử ở giữa < giá trị cần tìm, thuật toán tìm kiếm trong nửa thứ hai của danh sách.(bên phải phần tử ở giữa)

Thuật toán này tiếp tục chia đôi danh sách và tiếp tục tìm kiếm cho đến khi tìm thấy giá trị.

Lưu ý:

  • Độ phức tạp của thuật toán tìm kiếm nhị phân là O(log n). Thuật toán tìm kiếm nhị phân nhanh hơn rất nhiều so với tìm kiếm tuần tự vì nó chỉ phải xử lý log n lần thay vì n lần.
  • Các trường hợp không nên áp dụng thuật toán tìm kiếm nhị phân
    • Danh sách chưa được sắp xếp
    • Danh sách quá nhỏ (giảm hiệu suất)
    • Danh sách có các phần tử trùng lặp 

Giải thích qua ví dụ

Tìm kiếm phần tử  target= 8 trong mảng arr[]={1, 3, 4, 5, 8, 12, 23} bằng thuật toán tìm kiếm nhị phân

Lần 1: Khởi tạo L = 0 và R = n-1 = 6 (trong đó n=7 là độ dài của mảng), ta có M=(L+R)/2 = (0+6)/2=3

arr[] 1 3 4 5 8 12 23
index 0 1 2 3 4 5 6
L M R
  • So sánh giá trị của M với a ta thấy arr[M] = 5 < target = 8, chuyển không gian sang tìm kiếm bên phải của M

Lần 2: Lúc này, L = 4, R = 6 nên M=(L+R)/2 = (4+6)/2=5

arr[] 1 3 4 5 8 12 23
index 0 1 2 3 4 5 6
L M R
  • So sánh giá trị của M với target ta thấy arr[M] = 12 > target = 8, chuyển không gian sang tìm kiếm bên trái của M

Lần 3: Hiện tại, L = 4, R=4 nên M=(L+R)/2 = (4+4)/2=4

arr[] 1 3 4 5 8 12 23
index 0 1 2 3 4 5 6
L=R=M

So sánh ta thấy arr[M] = 8 = target = 8, đã tìm thấy mục tiêu tại vị trí 4.

Để bạn có thể hiểu rõ hơn, Kteam sẽ cho một ví dụ khác. Bạn hãy thử tự giải thích và trả lời đáp án vào bên dưới bình luận 

Ví dụ: Giải thích cách tìm kiếm nhị phân trên mảng arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, và mục tiêu cần tìm là 56. 


Định hướng cách làm

Để giải quyết bài toán, bạn có thể thực hiện các bước:

  1. Định nghĩa hàm binary_search(arr, x) nhận đầu vào là danh sách arr và giá trị tìm kiếm x.

  2. Khởi tạo biến leftright đại diện cho đoạn của danh sách mà chúng ta đang xét. Ban đầu, left được đặt bằng 0 và right được đặt bằng độ dài danh sách trừ 1.

  3. Bắt đầu vòng lặp while, trong đó chúng ta sẽ lặp lại cho đến khi left lớn hơn right.

  4. Tính chỉ số mid của phần tử ở giữa của đoạn đang xét bằng cách lấy trung bình của leftright và làm tròn xuống về số nguyên bằng toán tử //.

  5. So sánh phần tử ở chỉ số mid với giá trị tìm kiếm x. Nếu phần tử bằng x, trả về chỉ số mid.

  6. Nếu phần tử ở chỉ số mid nhỏ hơn giá trị tìm kiếm x, điều chỉnh biến left để bằng mid + 1 để tiếp tục tìm kiếm phía bên phải của mid.

  7. Nếu phần tử ở chỉ số mid lớn hơn giá trị tìm kiếm x, điều chỉnh biến right để bằng mid - 1 để tiếp tục tìm kiếm phía bên trái của mid.

  8. Nếu không tìm thấy giá trị tìm kiếm x trong danh sách, trả về -1.


Testcase

Bạn có thể sử dụng một số bộ test để kiểm tra tính đúng đắn của chương trình:

  • Test case 1: số cần tìm nằm ở giữa danh sách
arr1 = [1, 3, 5, 7, 9]
x1 = 5
print(binary_search(arr1, x1))  # Output: 2
  • Test case 2: số cần tìm nằm ở đầu danh sách
arr2 = [2, 4, 6, 8, 10]
x2 = 2
print(binary_search(arr2, x2))  # Output: 0
  • Test case 3: số cần tìm nằm ở cuối danh sách
arr3 = [11, 13, 15, 17, 19]
x3 = 19
print(binary_search(arr3, x3))  # Output: 4
  • Test case 4: số cần tìm không có trong danh sách
arr4 = [2, 4, 6, 8, 10]
x4 = 5
print(binary_search(arr4, x4))  # Output: -1
  • Test case 5: danh sách rỗng
arr5 = []
x5 = 2
print(binary_search(arr5, x5))  # Output: -1

Source code tham khảo

def binary_search(arr, x):
    """
    Hàm tìm kiếm nhị phân để tìm kiếm một phần tử trong danh sách được sắp xếp.
    Trả về chỉ số của phần tử nếu nó có trong danh sách, ngược lại trả về -1.
    """
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == x:
            return mid
        
        elif arr[mid] < x:
            left = mid + 1
            
        else:
            right = mid - 1
    
    return -1

Kết luận

Mặc dù bài giảng được hướng dẫn với ngôn ngữ python nhưng bạn hoàn toàn có thể diễn đạt bài toán này bằng các ngôn ngữ C++, C#, Java, ... một cách tương tự.

Nếu bạn có cách làm hiệu quả hơn / tối ưu hơn, hoặc cách diễn đạt dễ hiểu hơn hãy để lại source code hoặc hướng dẫn bên dưới bình luận để mọi người có thể tham khảo và học hỏi thêm.


Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

Nội dung bài viết

Tác giả/Dịch giả

K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Bài tập giải thuật với Python

Khoá học Bài tập giải thuật lập trình với Python  bao gồm 100 bài tập lập trình giải thuật từ cơ bản đến nâng cao, giúp bạn rèn luyện và nâng cao kỹ năng tư duy, tự giải quyết các vấn đề khi gặp một bài toán lập trình. 

Bạn hoàn toàn có thể tự mình giải quyết các bài toán hoặc tham khảo source code mẫu, debug, theo dõi hướng dẫn của Kteam để trau dồi kinh nghiệm xử lý của mình.

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.