Tìm kiếm là kỹ thuật chọn dữ liệu cụ thể từ tập hợp dữ liệu dựa trên một số điều kiện. Bạn đã quen với khái niệm này nếu bạn đã từng thực hiện tìm kiếm trên web để định vị các trang có chứa một số từ hoặc cụm từ. Tìm kiếm dữ liệu được lưu trữ trong các cấu trúc dữ liệu khác nhau là một phần rất quan trọng trong quá trình phát triển ứng dụng. Trong bài viết này, tôi sẽ thảo luận về hai thuật toán Tìm kiếm được sử dụng trong python
Thuật toán tìm kiếm nhị phân hiệu quả hơn nhiều so với thuật toán tìm kiếm tuyến tính. Ta cần sắp xếp mảng cho thuật toán tìm kiếm nhị phân không phải trường hợp trong thuật toán tìm kiếm tuyến tính. Sắp xếp mất một thời gian. Tuy nhiên, sử dụng thuật toán sắp xếp hiệu quả sẽ tạo thành một sự kết hợp tốt với thuật toán tìm kiếm nhị phânTrong cuộc sống hàng ngày, chúng ta không ngừng tìm kiếm thông tin hoặc cố gắng tìm giải pháp cho những vấn đề mình gặp phải.
Khi xem qua các kết quả tìm kiếm trên web, chúng tôi chọn các bài báo hoặc tài nguyên phù hợp nhất mà chúng tôi nghĩ sẽ giúp ích cho mình
Tìm kiếm là một phần trong cuộc sống của chúng ta vì không phải lúc nào chúng ta cũng có câu trả lời. Và có nhiều thuật toán giúp các chương trình chạy hiệu quả hơn và xử lý dữ liệu hiệu quả hơn
Những gì chúng tôi sẽ trình bày trong hướng dẫn này
- Thuật toán tìm kiếm là gì?
- Thuật toán tìm kiếm nhị phân là gì?
- Tìm kiếm nhị phân hoạt động như thế nào - Chia để trị
- Các quy trình liên quan đến thuật toán tìm kiếm nhị phân
- Các phương pháp được sử dụng trong thuật toán tìm kiếm nhị phân
- Các ví dụ thực tế về Tìm kiếm nhị phân
Thuật toán tìm kiếm là gì?
Thuật toán tìm kiếm hoạt động để truy xuất các mục từ bất kỳ cấu trúc dữ liệu nào. Nó so sánh dữ liệu đầu vào với thông tin được lưu trữ trong cơ sở dữ liệu của nó và đưa ra kết quả. Một ví dụ là tìm số của người bạn thân nhất của bạn trong danh sách liên lạc gồm 1.000 số của bạn
Có nhiều loại thuật toán tìm kiếm khác nhau. một số trong số họ là
Thuật toán tìm kiếm tuyến tính
Các thuật toán tìm kiếm tuyến tính là đơn giản nhất trong tất cả các thuật toán tìm kiếm. Như tên ngụ ý, chúng hoạt động theo trình tự
Tìm kiếm tuyến tính kiểm tra lần lượt các phần tử trong danh sách để tìm một giá trị khóa cụ thể. Giá trị khóa này nằm trong số các mục khác trong danh sách và thuật toán trả về vị trí bằng cách thực hiện kiểm tra
thuật toán Dijkstra
Thuật toán đường đi ngắn nhất của Dijkstra được sử dụng trong các tìm kiếm nâng cao hơn. Thuật toán Dijkstra vạch ra khoảng cách ngắn nhất giữa hai nút. Các nút này thường là các mạng định tuyến
Loại tìm kiếm này hữu ích khi bạn đang cố gắng tìm các tuyến đường trên bản đồ. Nó cung cấp cho bạn các tùy chọn dựa trên việc tìm đường đi ngắn nhất có thể
Thuật toán tìm kiếm nhị phân
Các thuật toán tìm kiếm nhị phân còn được gọi là tìm kiếm nửa khoảng thời gian. Chúng trả về vị trí của một giá trị đích trong danh sách được sắp xếp
Các thuật toán này sử dụng kỹ thuật “chia để trị” để tìm vị trí của giá trị
Thuật toán tìm kiếm nhị phân và thuật toán tìm kiếm tuyến tính là những ví dụ về thuật toán tìm kiếm đơn giản
Trong tìm kiếm nhị phân, phần tử ở giữa trong danh sách được tìm thấy trước khi so sánh với giá trị khóa mà bạn đang tìm kiếm. Nhưng trong tìm kiếm tuyến tính, các phần tử được lấy từng phần tử một trong danh sách bằng cách lặp qua và so sánh với giá trị khóa
Trong tìm kiếm nhị phân, danh sách được chia thành hai phần để lấy phần tử ở giữa. có phần bên trái, phần tử ở giữa và phần bên phải
Phía bên trái chứa các giá trị nhỏ hơn phần tử ở giữa và phía bên phải chứa các giá trị lớn hơn phần tử ở giữa. Phương pháp này sử dụng một danh sách được sắp xếp để làm việc
Một danh sách được sắp xếp có các mục được sắp xếp theo một thứ tự cụ thể. Để tìm kiếm hiệu quả cho tìm kiếm nhị phân, các giá trị trong danh sách phải được sắp xếp theo đúng thứ tự để đáp ứng quá trình tìm kiếm. Nếu một danh sách có các giá trị lẫn lộn, nó phải được sắp xếp theo thuật toán sắp xếp trước khi bạn thực hiện tìm kiếm
Thuật toán sắp xếp
Các thuật toán sắp xếp chấp nhận một danh sách chưa được sắp xếp làm đầu vào và trả về một danh sách với các phần tử được sắp xếp theo một thứ tự cụ thể [chủ yếu là thứ tự tăng dần]
Có nhiều loại thuật toán sắp xếp khác nhau, như sắp xếp chèn, sắp xếp nhanh, sắp xếp bong bóng và sắp xếp hợp nhất
Tìm kiếm nhị phân hoạt động như thế nào - Chia để trị
Thuật toán tìm kiếm nhị phân sử dụng một kỹ thuật gọi là "chia để trị" để giải quyết nhiệm vụ của nó. Thuật toán sắp xếp hợp nhất sử dụng kỹ thuật tương tự để sắp xếp các mục trong danh sách
Trong thuật toán tìm kiếm nhị phân, phương pháp “chia để trị” hoạt động theo cách này
- Thuật toán chia danh sách thành hai phần. bên trái và bên phải, được phân tách bằng phần tử ở giữa
- Nó tạo một biến để lưu trữ giá trị của mục cần tìm kiếm
- Nó chọn ra phần tử ở giữa và so sánh nó với phần tử cần tìm
- Nếu các mục được so sánh bằng nhau, thì quá trình kết thúc
- Nếu không, phần tử ở giữa lớn hơn hoặc nhỏ hơn mục bạn đang tìm kiếm. Nếu phần tử ở giữa lớn hơn, thuật toán sẽ tách danh sách và tìm kiếm phần tử ở phía bên trái. Nếu phần tử ở giữa nhỏ hơn, nó sẽ tách danh sách và tìm kiếm phần tử ở bên phải danh sách
Bạn có thể triển khai phương pháp này bằng cách sử dụng đệ quy hoặc lặp lại trong quy trình tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân hoạt động như thế nào - Từng bước
Trước tiên, trước khi thực hiện tìm kiếm, bạn cần sắp xếp danh sách
Sau đó, bạn tạo một biến lưu giá trị cần tìm
Tiếp theo, danh sách được chia thành hai phần. Ta tổng hợp chỉ số đầu và chỉ số cuối để tìm chỉ số của phần tử đứng giữa trong danh sách
Khi giá trị được tính toán của chỉ số phần tử ở giữa là một số float [như 3. 45], chúng tôi lấy toàn bộ phần làm chỉ số
Sau đó, chúng tôi so sánh giá trị mà chúng tôi đang tìm kiếm và phần tử ở giữa
Trường hợp sử dụng tìm kiếm nhị phân
Điều kiện 1
Nếu phần tử ở giữa bằng với giá trị cần tìm, vị trí của giá trị đó sẽ được trả về và quá trình kết thúc
if middle element == to_search
return position of middle element
*code ends*
Sử dụng hình ảnh trên làm ví dụ
Phần tử ở giữa = 23, giá trị đích/to_search = 23. So sánh hai giá trị ta thấy hai vế bằng nhau. 23 xuất hiện ở chỉ số 2 trong danh sách. Đó là đầu ra của mã và quá trình kết thúc
Điều kiện 2
Nếu phần tử ở giữa không bằng "to_search" thì ta kiểm tra các trường hợp sau
cảnh 1. nếu phần tử ở giữa lớn hơn giá trị cần tìm
if middle element > to_search
- tìm kiếm di chuyển sang bên trái vì các giá trị nhỏ hơn phần tử ở giữa
- vị trí của phần tử ở giữa dịch chuyển sang trái 1
- new_position = index[phần tử ở giữa] - 1
- một tìm kiếm mới bắt đầu và tìm kiếm kết thúc ở vị trí mới đó và nó nhận tất cả các giá trị trước nó
Sử dụng hình ảnh trên làm ví dụ
middle element = 23
to_search = 4
if 23 > 4
- chúng tôi di chuyển sang phía bên trái vì tất cả các số nhỏ hơn 23 được lưu trữ ở đó. chỉ số [23] = 2
- new_position = index[23] - 1 = 2-1 = 1
- Quá trình tìm kiếm sẽ kết thúc ở chỉ mục 1 và lấy tất cả [các] giá trị khác trước chỉ mục 1
So sánh phần tử ở giữa mới [4] với phần tử đích [4] ta thấy chúng bằng nhau. Vì vậy, quá trình tìm kiếm kết thúc và đầu ra là vị trí "4" chiếm trong danh sách [là chỉ số 0]
kịch bản 2. nếu phần tử ở giữa nhỏ hơn giá trị cần tìm
if middle element < to_search
- tìm kiếm di chuyển sang bên phải vì các giá trị lớn hơn phần tử ở giữa
- vị trí của phần tử ở giữa dịch chuyển sang phải 1
- new_position = index[phần tử ở giữa] + 1
- một tìm kiếm mới bắt đầu ở vị trí mới và kết thúc ở chỉ mục cuối cùng trong danh sách
- tất cả các giá trị được lấy từ vị trí mới đến cuối danh sách
Sử dụng Hình ảnh đầu tiên làm ví dụ
middle element = 23
to_search = 32
if 23 > 32
- chúng tôi di chuyển sang phía bên phải vì tất cả các số lớn hơn 23 được lưu trữ ở đó. chỉ số[23] = 2 ,
- new_position = index[23] + 1 = 2+1 = 3
- Quá trình tìm kiếm sẽ bắt đầu ở chỉ mục 3 và lấy tất cả [các] giá trị khác sau chỉ mục 3
So sánh phần tử ở giữa [32] với phần tử đích [32] ta thấy chúng bằng nhau. Vì vậy, quá trình tìm kiếm kết thúc và đầu ra là vị trí "4" chiếm trong danh sách [chỉ mục 4]
Các phương thức được sử dụng trong thuật toán tìm kiếm nhị phân
Có hai phương pháp có thể thực hiện kỹ thuật “chia để trị” trong tìm kiếm. Chúng là phép lặp và đệ quy
Lặp lại là gì?
Để lấy các phần tử từ một bộ, danh sách hoặc từ điển, bạn lặp qua các mục bằng các vòng lặp
Lặp lại là một chuỗi các câu lệnh được lặp đi lặp lại trong quá trình thực thi và nó có số lượng giá trị có thể đếm được. Ví dụ, khi lặp qua danh sách ngẫu nhiên, chúng ta lặp qua biến thực chứa danh sách để lấy giá trị
Triển khai mã cho tìm kiếm nhị phân với phép lặp
Đây là mã
def binary_search[list_num , to_search]:
first_index = 0
size = len[list_num]
last_index = size - 1
mid_index = [first_index + last_index] // 2
# print[mid_index]
mid_element = list_num[mid_index]
# print[mid_element]
is_found = True
while is_found:
if first_index == last_index:
if mid_element != to_search:
is_found = False
return " Does not appear in the list"
elif mid_element == to_search:
return f"{mid_element} occurs in position {mid_index}"
elif mid_element > to_search:
new_position = mid_index - 1
last_index = new_position
mid_index = [first_index + last_index] // 2
mid_element = list_num[mid_index]
if mid_element == to_search:
return f"{mid_element} occurs in position {mid_index}"
elif mid_element < to_search:
new_position = mid_index + 1
first_index = new_position
last_index = size - 1
mid_index = [first_index + last_index] // 2
mid_element = list_num[mid_index]
if mid_element == to_search:
return f"{mid_element} occurs in position {mid_index}"
list_container = [16 , 18 , 20 , 50 , 60 , 81 , 84 , 89]
print[binary_search[list_container , 81]]
print[binary_search[list_container , 10]]
Bây giờ hãy xem những gì đang xảy ra ở đây
- Đầu tiên, chúng tôi chuyển vào một danh sách và một giá trị được tìm kiếm [to_search] làm đầu vào cho một hàm
- Trong hàm, chúng ta tạo một tên biến của chỉ mục đầu tiên và gán nó là "0". Chỉ mục đầu tiên trong danh sách luôn là "0"
- Sau đó, chúng tôi tạo bốn tên biến. "size" để lưu độ dài của danh sách, "last_index" để lưu chỉ mục của phần tử cuối cùng, "mid_index" để lưu hoạt động tìm chỉ mục phần tử ở giữa và "mid_element" để lưu phần tử ở giữa lấy từ danh sách
- Sau đó, chúng tôi giới thiệu một vòng lặp while để làm cho các điều kiện chạy lặp lại. Phía trên vòng lặp while, chúng ta tạo một tên biến "is_found" và đặt nó thành "True". Điều kiện này kiểm tra xem "mục cần tìm" có được tìm thấy hay không
- Trong vòng lặp while, chúng tôi kiểm tra tất cả các điều kiện. Điều kiện đầu tiên là kiểm tra xem phần tử ở giữa và biến "to_search" có bằng nhau không. Nếu chúng bằng nhau, vị trí của phần tử sẽ được trả về
- Sau đó, chúng tôi kiểm tra điều kiện thứ hai [nếu phần tử ở giữa. = mục được tìm kiếm] dẫn chúng ta đến hai kịch bản.
– nếu phần tử ở giữa lớn hơn phần tử cần tìm, vị trí mới sẽ dịch chuyển sang trái một lần. Việc tìm kiếm sẽ bắt đầu từ chỉ mục đầu tiên và kết thúc ở vị trí mới là chỉ mục cuối cùng mới.
– Nếu phần tử ở giữa nhỏ hơn phần tử cần tìm, vị trí mới sẽ dịch chuyển sang phải một lần. Tìm kiếm sẽ bắt đầu từ vị trí mới là chỉ mục đầu tiên mới và kết thúc ở chỉ mục cuối cùng.
Khi kết thúc các tình huống này, chúng tôi kiểm tra xem phần tử ở giữa mới có giống với mục cần tìm không. Nếu trùng sẽ trả về vị trí của hàng. Nếu không, các điều kiện được kiểm tra cho đến khi các giá trị bằng nhau
Để xử lý lỗi, giả sử chúng ta muốn tìm kiếm một giá trị không xuất hiện trong danh sách. Nếu chúng ta kết thúc ở hai điều kiện, vòng lặp sẽ tiếp tục chạy và cuối cùng có thể làm hỏng hệ thống
Để bắt lỗi ta đặt điều kiện kiểm tra xem chỉ số đầu có bằng chỉ số cuối không. Sau đó ta kiểm tra xem phần tử ở giữa có bằng với đối tượng cần tìm không. Nếu nó không bằng nhau, "được tìm thấy" sẽ là "Sai". Khi bạn chạy cái này, nó sẽ hiển thị một mảng trống. Trong mã của tôi, đầu ra là một tuyên bố
Bước cuối cùng là gọi hàm và kết quả được hiển thị
Và đây là kết quả
Nếu phần tử nằm trong danh sách, đầu ra là vị trí
Nếu phần tử không có trong danh sách, đầu ra là một câu lệnh như thế này
Recursion là gì?
Một hàm được gọi là đệ quy nếu nó tham chiếu đến chính nó hoặc [các] thuật ngữ trước đó để giải quyết một tác vụ
Một hàm đệ quy được lặp đi lặp lại và nó được thực hiện theo trình tự. Nó bắt đầu từ một vấn đề phức tạp và chia nhỏ mọi thứ thành một dạng đơn giản hơn
Triển khai mã cho tìm kiếm nhị phân với đệ quy
Với đệ quy, nó đơn giản hơn một chút và yêu cầu ít mã hơn. Đây là những gì nó trông giống như
def binary_search[list_num, first_index, last_index, to_search]:
if last_index >= first_index:
mid_index = [first_index + last_index] // 2
mid_element = list_num[mid_index]
if mid_element == to_search:
return f"{mid_element} occurs in position {mid_index}"
elif mid_element > to_search:
new_position = mid_index - 1
# new last index is the new position
return binary_search[list_num, first_index, new_position, to_search]
elif mid_element < to_search:
new_position = mid_index + 1
# new first index is the new position
return binary_search[list_num, new_position, last_index, to_search]
else:
return " Does not appear in the list"
list_container = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
search = 34
first = 0
last= len[list_container] - 1
print[binary_search[list_container,first,last,search]]
- Đầu tiên, một chức năng chấp nhận bốn đầu vào. chỉ mục đầu tiên, chỉ mục cuối cùng, danh sách và to_search [mục được tìm kiếm]
- Sau đó, chúng tôi kiểm tra xem giá trị của chỉ mục cuối cùng có lớn hơn hoặc bằng giá trị của chỉ mục đầu tiên không. Nếu điều kiện đúng ta gán thao tác tìm chỉ số phần tử ở giữa cho tên biến “mid_index”. Sau đó, phần tử ở giữa được lấy từ danh sách bằng cách sử dụng chỉ số ở giữa làm vị trí
- Chúng tôi tạo một câu lệnh "if" bên dưới khối "if" đầu tiên để kiểm tra xem phần tử ở giữa và biến "to_search" có bằng nhau không. Nếu chúng bằng nhau, vị trí của phần tử sẽ được trả về
- Sau đó, chúng tôi kiểm tra điều kiện thứ hai, [nếu phần tử ở giữa. = mục được tìm kiếm] dẫn chúng ta đến hai kịch bản.
– nếu phần tử ở giữa lớn hơn phần tử cần tìm, vị trí mới sẽ dịch chuyển sang trái một lần. Việc tìm kiếm sẽ bắt đầu từ chỉ mục đầu tiên và kết thúc ở vị trí mới. Chúng tôi trả về hàm và chuyển vào vị trí mới làm giá trị chỉ mục cuối cùng.
– nếu phần tử ở giữa nhỏ hơn phần tử cần tìm, vị trí mới sẽ dịch chuyển sang phải một lần. Việc tìm kiếm sẽ bắt đầu từ vị trí mới và kết thúc ở chỉ mục cuối cùng. Chúng tôi trả về hàm và chuyển vào vị trí mới làm giá trị chỉ mục đầu tiên. - Điều kiện cuối cùng sẽ được thụt lề giống như câu lệnh "if" đầu tiên. Nếu to_search không có trong danh sách, nó sẽ trả về một câu lệnh
Bước cuối cùng là gọi hàm và kết quả được hiển thị
Và đây là kết quả
Nếu phần tử nằm trong danh sách, đầu ra là vị trí
Nếu phần tử không có trong danh sách, đầu ra là một câu lệnh
Các ví dụ thực tế về tìm kiếm nhị phân
Bạn có thể không nhận ra, nhưng chúng tôi luôn thực hiện tìm kiếm nhị phân. Dưới đây là một vài ví dụ về cách bạn có thể sử dụng hoặc gặp nó trong cuộc sống hoặc công việc hàng ngày của mình
- Tìm kiếm một từ trong từ điển
- tìm kiếm một cuốn sách văn học trong phần văn học trong thư viện
- tìm kiếm một phần tử trong một danh sách được sắp xếp
- tìm kiếm những học sinh cao hơn 5 feet 3 inch trong một hàng học sinh được sắp xếp theo chiều cao của họ
Sự kết luận
Ở cuối bài viết này, bạn nên làm quen với cách hoạt động của các thuật toán tìm kiếm nhị phân và cách triển khai chúng trong mã
Nếu bạn không thể nắm bắt mọi thứ cùng một lúc cũng không sao – chỉ cần cho bản thân một chút thời gian và thực hành. Nếu bạn gặp bất kỳ lỗi nào hoặc có thắc mắc, bạn có thể liên hệ với tôi trên Twitter
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
QUẢNG CÁO
Đọc thêm bài viết
Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn
Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu