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

Tự học Cấu trúc dữ liệu và giải thuật với Python

5.0 (1 đánh giá)

Tạo bởi Kteam Cập nhật lần cuối 2 năm trước 10.478 lượt xem 1 bình luận

Tác giả/Dịch giả:

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

Nội dung bài viết Học nhanh

Yêu cầu bài toán
Thuật toán tìm kiếm nhị phân
- Giải thích qua ví dụ
Định hướng cách làm
Testcase
Source code tham khảo
Kết luận
Tải xuống
- Tài liệu
Thảo luận

Bài trước Bài sau

Yêu cầu bài toá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. Vì vậy, yêu cầu để áp dụng thuật toán tìm kiếm nhị phân là danh sách cần được sắp xếp theo thứ tự tăng hoặc giả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 lý 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 trá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 phả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 ý:

Độ 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.
Các trường hợp không nên áp dụng thuật toán tìm kiếm nhị 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

Giải thích qua ví dụ

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 tạo L = 0 và R = n-1 = 6 (trong đó n=7 là độ dài của mảng), ta có 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 sánh giá trị của M với a ta thấy arr[M] = 5 < target = 8, chuyển không gian sang tìm kiếm bên phải của M

Lần 2: Lúc nà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 sánh giá trị của M với target ta thấy arr[M] = 12 > target = 8, chuyển không gian sang tìm kiếm bên trái của M

Lần 3: Hiện tạ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 sánh ta thấy arr[M] = 8 = target = 8, đã tìm thấy mục tiêu tại vị trí 4.

Để bạn có thể hiểu rõ hơn, Kteam sẽ cho một ví dụ khác. Bạn hãy thử tự giải thích và trả lời đáp án vào bên dưới bình luận

Ví dụ: Giải thích cách tìm kiếm nhị phân trên mảng arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, và mục tiêu cần tìm là 56.

Định hướng cách làm

Để giải quyết bài toán, bạn có thể thực hiện các bước:

Đị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.
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.
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.
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ử //.
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.
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.
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.
Nếu không tìm thấy giá trị tìm kiếm x trong danh sách, trả về -1.

Testcase

Bạn có thể sử dụ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

makefile


arr1 = [1, 3, 5, 7, 9]
x1 = 5
print(binary_search(arr1, x1))  # Output: 2
1
2
3

Test case 2: số cần tìm nằm ở đầu danh sách

makefile


arr2 = [2, 4, 6, 8, 10]
x2 = 2
print(binary_search(arr2, x2))  # Output: 0
1
2
3

Test case 3: số cần tìm nằm ở cuối danh sách

makefile


arr3 = [11, 13, 15, 17, 19]
x3 = 19
print(binary_search(arr3, x3))  # Output: 4
1
2
3

Test case 4: số cần tìm không có trong danh sách

makefile


arr4 = [2, 4, 6, 8, 10]
x4 = 5
print(binary_search(arr4, x4))  # Output: -1
1
2
3

Test case 5: danh sách rỗng

makefile


arr5 = []
x5 = 2
print(binary_search(arr5, x5))  # Output: -1
1
2
3

Source code tham khảo

Python


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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Kết luận

Mặc dù bài giảng được hướng dẫn với ngôn ngữ python nhưng bạn hoàn toàn có thể diễn đạt bài toán này bằng các ngôn ngữ C++, C#, Java, ... một cách tương tự.

Nếu bạn có cách làm hiệu quả hơn / tối ưu hơn, hoặc cách diễn đạt dễ hiểu hơn hãy để lại source code hoặc hướng dẫn bên dưới bình luận để mọi người có thể tham khảo và học hỏi thêm.

Tải xuống

Tài liệu

Nhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung 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 dưới dạng file PDF trong link bên dưới.

Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com

Đừng quên like và share để ủng hộ Kteam và tác giả nhé!

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.

CỘNG ĐỒNG HỎI ĐÁP HOWKTEAM.COM

GROUP THẢO LUẬN FACEBOOK

Nội dung bài viết

Yêu cầu bài toán
Thuật toán tìm kiếm nhị phân
- Giải thích qua ví dụ
Định hướng cách làm
Testcase
Source code tham khảo
Kết luận
Tải xuống
- Tài liệu
Thảo luận

Tác giả/Dịch giả

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa họ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 đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng!

Khóa học

Tự học Cấu trúc dữ liệu và giải thuật với Python

Giới thiệu khóa học

Là một trong những ngôn ngữ được sử dụng phổ biến nhất trên thế giới, Python sở hữu cộng đồng người dùng khổng lồ và là công cụ đắc lực của rất nhiều lập trình viên nhờ sức hút đến từ sự dễ hiểu, tiện lợi và vô cùng linh hoạt. Áp dụng trong nhiều lĩnh vực từ đơn giản đến phức tạp: xây dựng các trang web và phát triển phần mềm, sử dụng Python trong Machine learning & Data science, xây dựng các model AI với python....

Cấu trúc dữ liệu và giải thuật là một bộ môn nền tảng và có ý nghĩa vô cùng quan trọng đối với các lập trình viên, nó cung cấp cho chúng ta các kiến thức và kỹ năng cần thiết để có thể lưu trữ và thao tác với dữ liệu một cách hiệu quả. Việc nắm vững bộ môn này sẽ giúp cho chúng ta dễ dàng tiếp cận với các kiến thức mới ở mức độ khó hơn, cũng như là cải thiện khả năng tư duy thực chiến.

Cấu trúc dữ liệu và giải thuật, như tên của mình, thì bao gồm hai thành phần:

Cấu trúc dữ liệu: chính là thứ mà ta dùng để lưu trữ dữ liệu trong máy tính. Từ những loại cấu trúc dữ liệu đơn giản như là số, chuỗi hay là mảng, thì chúng ta sẽ cải biến chúng nhằm lưu trữ các dạng dữ liệu phức tạp hơn như là cây, đồ thị hay là danh sách liên kết.
Giải thuật: là các phương pháp, cách thức mà ta sẽ dùng để xử lý các vấn đề. Thuần thục được các thuật toán sẽ giúp chúng ta cải thiện được khả năng tư duy và có thể xử lý được vấn đề theo cách hiệu quả và tối ưu.

Trong khóa học này, Kteam sẽ cung cấp cho các bạn những kiến thức cơ bản và là nền tảng của bộ môn cấu trúc dữ liệu và giải thuật, với loại ngôn ngữ lập trình chính mà ta sử dụng là python.

Từ khóa học này, các bạn hoàn toàn có thể đủ tự tin và kiến thức để tiếp cận những kiến thức của bộ môn cấu trúc dữ liệu và giải thuật ở trình độ cao hơn.

Đối tượng tham gia

Các bạn sẽ cần nắm vững được những kiến thức cơ bản về cú pháp và các thao tác cơ bản với python. Bên cạnh đó, cũng sẽ cần một chút kiến thức toán học cơ bản để đảm bảo rằng bạn có thể nắm vững kiến thức của khóa học.

Nếu các bạn là một người mới bắt đầu học python thì hoàn toàn có thể học song song hai khóa học, để vừa có thể củng cố kiến thức với python, vừa tiếp thu thêm được các kiến thức về cấu trúc dữ liệu và giải thuật.

Kiến thức truyền tải

Trong khóa học, bạn sẽ được tiếp cận đến các nhóm kiến thức như sau:

Cấu trúc dữ liệu

Kteam sẽ gửi đến các bạn các kiến thức về các loại cấu trúc dữ liệu thú vị như là danh sách liên kết, đồ thị, cây, và heap. Đây là những loại cấu trúc dữ liệu khá dễ hiểu và từ những loại cấu trúc dữ liệu này, các bạn có thể tìm hiểu về các loại cấu trúc dữ liệu đặc thù hơn, ví dụ như là Fibonacci heap, cây AVL, ...

Giải thuật

Trong nội dung khóa học, bạn sẽ được cung cấp các kiến thức về các kỹ thuật để xử lý bài toán. Từ những kỹ thuật như là phương pháp sinh, nhánh cận cho tới những kỹ thuật mạnh mẽ hơn như là quy hoạch động, tất cả đều sẽ có ở trong nội dung của khóa học.

Toán học

Toán học cũng là một phần đóng vai trò quan trọng trong bộ môn cấu trúc dữ liệu và giải thuật. Việc nắm vững các kiến thức về toán học sẽ giúp ta dễ dàng hơn trong việc xử lý các vấn đề của bộ môn này. Và, toán học cũng sẽ giúp các bạn cải thiện khả năng tư duy. Trong nội dung của khóa học, chúng mình sẽ không đi quá sâu về toán mà chỉ đề cập đến những thành phần cơ bản. Các bạn có thể xem những kiến thức mà tụi mình đề cập như là một “keyword” để các bạn có thể tìm hiểu thêm về những đơn vị toán đó.

Cấu trúc khóa học

Khóa học sẽ gửi đến các bạn một lượng kiến thức lớn và được truyền tải xuyên suốt các bài của khóa. Để các bạn có thể dễ dàng hơn trong cách tiếp cận nội dung, thì các bài trong khóa sẽ được chia thành ba dạng:

Dạng A: Bao gồm các bài có nội dung là phần giới thiệu về những mảng kiến thức cố định. Các bài này sẽ cung cấp cho các bạn cái nhìn tổng quan nhất về đơn vị kiến thức thuộc một chủ đề nhất định. Ví dụ: với bài “Giới thiệu về đồ thị”, thì Kteam sẽ giới thiệu cho các bạn những khái niệm sơ khai nhất liên quan đến đồ thị như là đỉnh, cạnh, đường đi, chu trình, ...
Dạng B: Gồm các bài tập có liên quan đến những chủ đề được giới thiệu trong bài A. Các bài này là những bài tập đi kèm giúp các bạn có khả năng sử dụng những kiến thức thu được từ các bài A và C để áp dụng vào việc xử lý một bài toán nào đó.
Dạng C: Các bài thuộc dạng này sẽ là những bài mà chúng ta sẽ cùng nhau đi sâu hơn về những chủ đề được giới thiệu ở bài A. Ví dụ như liên quan đến lý thuyết đồ thị, chúng ta sẽ có những kiến thức sâu hơn như là tìm kiếm đường đi trong đồ thị, tìm cây khung nhỏ nhất, ....

Về tác giả

Khóa học này được biên soạn bởi Nông Thanh Toàn. Tuy không phải là chuyên gia về lập trình và giải thuật, nhưng tác giả lại đam mê và mong muốn phát triển bản thân thông qua việc tìm hiểu và chia sẻ kiến thức. Với tinh thần này, tác giả đã tạo ra khóa học để chia sẻ kiến thức của mình với những người mới bắt đầu học lập trình và đang muốn tiếp cận với bộ môn cấu trúc dữ liệu và giải thuật.

Đánh giá

Nguyễn Thị Thu Hà đã đánh giá 2 năm trước

Báo cáo

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

Nguyễn Thị Thu Hà đã bình luận 2 năm trước

CÒn nhiều bài tập với giải thuật nữa không ạ em xin link với ạ . Hi vọng add sẽ tạo web gắn thêm link những bài tập nữa ở dưới trang cho dễ tìm ạ . Hay do em mới sử dụng web nên tìm tiếm bài tập để kèm thêm mà tìm mãi mới có của web hihi.

Trả lời Báo cáo

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

Tự học Cấu trúc dữ liệu và giải thuật với Python

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

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 bài toán

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

Giải thích qua ví dụ

Định hướng cách làm

Testcase

Source code tham khảo

Kết luận

Tải xuống

Tài liệu

Thảo luận

Tác giả/Dịch giả

Khóa học

Giới thiệu khóa học

Đánh giá

Bình luận

Danh sách bài giảng

Không có video.

AD BLOCKER DETECTED