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 left và right đạ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 left và right 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ÌNH LUẬ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.