Trong hướng dẫn về python này, bạn sẽ tìm hiểu về tìm kiếm nhị phân và tìm kiếm tuyến tính trong python với các ví dụ. Ở đây chúng tôi sẽ kiểm tra
- Tìm kiếm nhị phân trong python là gì?
- Tìm kiếm nhị phân trong python mà không cần đệ quy
- Tìm kiếm nhị phân đệ quy Python
- Tìm kiếm nhị phân Python bằng thư viện tìm lần xuất hiện đầu tiên của một phần tử
- Tìm kiếm nhị phân Python bằng thư viện tìm giá trị lớn nhất nhỏ hơn n
- Tìm kiếm tuyến tính trong python
- Tìm kiếm tuyến tính trong python bằng danh sách
- Tìm kiếm tuyến tính vs Tìm kiếm nhị phân trong python
Mục lục
- Tìm kiếm nhị phân trong python là gì?
- Tìm kiếm nhị phân trong python mà không cần đệ quy
- Tìm kiếm nhị phân đệ quy Python
- Tìm kiếm nhị phân Python bằng thư viện tìm lần xuất hiện đầu tiên của một phần tử
- Tìm kiếm nhị phân Python bằng thư viện tìm giá trị lớn nhất nhỏ hơn n
- Tìm kiếm tuyến tính trong python
- Tìm kiếm tuyến tính trong python bằng danh sách
- Tìm kiếm tuyến tính vs Tìm kiếm nhị phân trong python
Tìm kiếm nhị phân trong python là gì?
- Tìm kiếm nhị phân là một thuật toán được sử dụng để tìm vị trí của một phần tử trong một mảng có thứ tự
- Có hai cách để thực hiện tìm kiếm nhị phân. Trong cả hai cách tiếp cận, chúng tôi có vị trí cao nhất và thấp nhất trong một mảng
- Cách tiếp cận đầu tiên là phương pháp lặp và cách tiếp cận thứ hai là phương pháp đệ quy
- Tìm kiếm nhị phân là một cách hiệu quả để tìm kiếm thông qua danh sách các số, nó hiệu quả hơn tìm kiếm tuyến tính vì nó cắt giảm tìm kiếm xuống một nửa
Tìm kiếm nhị phân trong python mà không cần đệ quy
Trong tìm kiếm nhị phân Python, chúng tôi sẽ đưa ra một danh sách được sắp xếp và chúng tôi sẽ tìm phần tử bằng cách sử dụng tìm kiếm nhị phân. Trong một phương pháp lặp, chúng tôi sẽ lặp qua mọi mục trong danh sách của mình, tìm giá trị ở giữa và tiếp tục thực hiện cho đến khi tìm kiếm hoàn tất
Ví dụ
def binary_searchiter[arr, n]:
low = 0
high = len[arr] - 1
mid = 0
while low n:
high = mid - 1
else:
return mid
return -1
arr = [4, 7, 9, 16, 20, 25]
n = 7
r = binary_searchiter[arr, n]
if r != -1:
print["Element found at index", str[r]]
else:
print["Element is not present in array"]Sau khi viết đoạn mã trên [tìm kiếm nhị phân trong python mà không cần đệ quy], Những cái bạn sẽ in thì đầu ra sẽ xuất hiện dưới dạng “Phần tử được tìm thấy ở chỉ mục 1”. Ở đây, phương pháp lặp được sử dụng để tìm số trong danh sách
Bạn có thể tham khảo ảnh chụp màn hình bên dưới để tìm kiếm nhị phân trong python mà không cần đệ quy
Tìm kiếm nhị phân đệ quy Python
Chúng ta cũng có thể sử dụng đệ quy để tìm kiếm nhị phân trong Python. Trong tìm kiếm nhị phân đệ quy, chúng ta sẽ định nghĩa một hàm, hàm này sẽ tự gọi chính nó cho đến khi thỏa mãn điều kiện. Trước tiên, chúng tôi sẽ tính số ở giữa và tiếp tục thực hiện cho đến khi tìm kiếm hoàn tất
Ví dụ
def binary_search[arr, low, high, number]:
if high >= low:
mid = [high + low] // 2
if arr[mid] == number:
return mid
elif arr[mid] > number:
return binary_search[arr, low, mid-1, number]
else:
return binary_search[arr, mid+1, high, number]
else:
return -1
arr = [5, 12, 17, 19, 22, 30]
number = 22
r = binary_search[arr, 0, len[arr]-1, number]
if r != -1:
print["Element found at index", str[r]]
else:
print["Element is not present in array"] Sau khi viết đoạn mã trên [tìm kiếm nhị phân đệ quy python], Những cái bạn sẽ in thì đầu ra sẽ xuất hiện dưới dạng “ Phần tử được tìm thấy ở chỉ mục 4 ”. Ở đây, phương pháp đệ quy được sử dụng và chúng tôi đang chuyển hai tham số mới cho hàm binary_search của mình
Bạn có thể tham khảo ảnh chụp màn hình bên dưới để tìm kiếm nhị phân đệ quy python
Tìm kiếm nhị phân Python bằng thư viện tìm lần xuất hiện đầu tiên của một phần tử
Trong phần này, chúng tôi sẽ sử dụng chức năng thư viện để thực hiện tìm kiếm nhị phân, chúng tôi cần nhập “từ bisect nhập bisect_left” và chia đôi. Hàm bisect_left[a, n] dùng để trả về điểm chèn ngoài cùng bên trái của n trong danh sách đã sắp xếp
Ví dụ
from bisect import bisect_left
def Binary_Search[a, n]:
i = bisect_left[a, n]
if i != len[a] and a[i] == n:
return i
else:
return -1
a = [2, 5, 5, 6, 10]
n = int[5]
val = Binary_Search[a, n]
if val == -1:
print[n, "is not present"]
else:
print["First occurence of", n, "is present at", val]Sau khi viết đoạn mã trên [tìm kiếm nhị phân python sử dụng thư viện tìm lần xuất hiện đầu tiên của một phần tử], Sau khi bạn in thì đầu ra sẽ xuất hiện dưới dạng "Lần xuất hiện đầu tiên của 5 là 1". Ở đây, bằng cách sử dụng hàm bisect_left[], nó sẽ trả về lần xuất hiện đầu tiên của phần tử có trong danh sách
Bạn có thể tham khảo ảnh chụp màn hình bên dưới tìm lần xuất hiện đầu tiên của một phần tử
Tìm kiếm nhị phân Python bằng thư viện tìm giá trị lớn nhất nhỏ hơn n
Chúng ta có thể lấy giá trị lớn hơn, nhỏ hơn n bằng cách sử dụng hàm bisect_left[]
Ví dụ
from bisect import bisect_left
def Binary_search[a, n]:
i = bisect_left[a, n]
if i :
return i-1
else:
return -1
a = [2, 4, 6, 8, 10, 12]
n = int[10]
val = Binary_search[a, n]
if val == -1:
print[n, "is not present"]
else:
print["Larger value, smaller than", n, "is at position", val]Sau khi viết đoạn mã trên [tìm kiếm nhị phân python sử dụng thư viện tìm giá trị lớn nhất nhỏ hơn n], Sau khi bạn in thì đầu ra sẽ xuất hiện dưới dạng “Giá trị lớn hơn, nhỏ hơn 10 ở vị trí 3”. Ở đây, bằng cách sử dụng hàm bisect_left[], nó sẽ trả về giá trị lớn hơn nhỏ hơn n
Bạn có thể tham khảo ảnh chụp màn hình bên dưới để tìm giá trị lớn nhất nhỏ hơn n
Tìm kiếm tuyến tính trong python
Tìm kiếm tuyến tính trong Python là loại thuật toán tìm kiếm cơ bản nhất. Tìm kiếm tuyến tính hoặc tuần tự được thực hiện khi bạn tìm kiếm từng mục trong danh sách từ đầu đến cuối để tìm kết quả phù hợp với những gì bạn đang tìm kiếm
Ví dụ
def linear_search[arr, n]:
for i in range[len[arr]]:
if arr[i] == n:
return i
return -1
arr = [3, 2, 6, 19, 15, 20]
n = 15
r = linear_search[arr, n]
if[r == -1]:
print["Element not found"]
else:
print["Element found at index",str[r]]Sau khi viết đoạn mã trên [tìm kiếm tuyến tính trong python], Ones bạn sẽ in sau đó đầu ra sẽ xuất hiện dưới dạng “ Element found at index 4 ”. Ở đây, một tìm kiếm tuyến tính được sử dụng để tìm kiếm phần tử trong danh sách theo thứ tự tuần tự và nếu chúng ta tìm thấy phần tử thì nó sẽ trả về chỉ mục của phần tử cụ thể đó
Bạn có thể tham khảo ảnh chụp màn hình bên dưới để tìm kiếm tuyến tính trong python
Tìm kiếm tuyến tính trong python bằng danh sách
Để thực hiện tìm kiếm tuyến tính trên một danh sách trong Python thì chúng ta phải bắt đầu từ phần tử ngoài cùng bên trái của danh sách sau đó nó sẽ so sánh với từng phần tử trong danh sách, nếu phần tử khớp thì nó sẽ cho vị trí còn không thì nó sẽ trả về không.
Ví dụ
pos = -1
def linear_search[list,number]:
for i in range[len[list]]:
if list[i] == number:
globals[] ['pos'] = i
return True
return False
list = ['Welcome', 2, 'Python', 5]
number = 5
if linear_search[list, number]:
print["Found the element",pos]
else:
print["Not Found"]Sau khi viết đoạn mã trên [tìm kiếm tuyến tính trong python bằng cách sử dụng danh sách], Sau khi bạn in thì đầu ra sẽ xuất hiện dưới dạng “Đã tìm thấy phần tử tại chỉ mục 3”. Ở đây, tìm kiếm tuyến tính sử dụng danh sách được sử dụng để tìm kiếm phần tử trong danh sách theo thứ tự tuần tự và nếu chúng ta tìm thấy phần tử thì nó sẽ trả về chỉ mục của phần tử cụ thể đó
Bạn có thể tham khảo ảnh chụp màn hình bên dưới để tìm kiếm tuyến tính trong python bằng cách sử dụng danh sách
Tìm kiếm tuyến tính vs Tìm kiếm nhị phân trong python
Tìm kiếm tuyến tínhTìm kiếm nhị phânTìm kiếm tuyến tính có tính chất lặp đi lặp lại và sử dụng cách tiếp cận tuần tự. Tìm kiếm nhị phân thực hiện cách tiếp cận phân chia và chinh phục. Thời gian tốt nhất trong tìm kiếm tuyến tính là dành cho phần tử đầu tiên i. đ, O[1]. Trong tìm kiếm nhị phân, trường hợp tốt nhất là dành cho phần tử ở giữa i. e, O[1] Độ phức tạp thời gian của tìm kiếm tuyến tính là O[N]. Độ phức tạp thời gian cho tìm kiếm nhị phân là O[log N]. Tìm kiếm tuyến tính rất dễ sử dụng. Tìm kiếm nhị phân là khó khăn. Trong một tìm kiếm tuyến tính, không cần bất kỳ thứ tự nào. Trong một tìm kiếm nhị phân, nó là cần thiết để được sắp xếp theo thứ tự. Tìm kiếm tuyến tính vs Tìm kiếm nhị phân trong pythonBạn có thể thích các hướng dẫn Python sau đây
- Python chuyển đổi danh sách thành chuỗi
- Kiểm tra xem một danh sách có trống trong Python không
- Lỗi loại Python. đối tượng 'danh sách' không thể gọi được
- Python chuyển đổi tuple thành danh sách
- Tích vô hướng và tích chéo trong Python
- Lệnh thoát Python [thoát[], thoát[], sys. lối ra[]]
- Đầu vào Python và hàm raw_input
- Python đọc một tệp nhị phân
Trong hướng dẫn này, chúng ta đã tìm hiểu về tìm kiếm nhị phân và tìm kiếm tuyến tính trong Python đồng thời chúng ta cũng đã biết cách sử dụng nó với một ví dụ như
- Tìm kiếm nhị phân trong python là gì?
- Tìm kiếm nhị phân trong python mà không cần đệ quy
- Tìm kiếm nhị phân đệ quy Python
- Tìm kiếm nhị phân Python bằng thư viện tìm lần xuất hiện đầu tiên của một phần tử
- Tìm kiếm nhị phân Python bằng thư viện tìm giá trị lớn nhất nhỏ hơn n
- Tìm kiếm tuyến tính trong python
- Tìm kiếm tuyến tính trong python bằng danh sách
- Tìm kiếm tuyến tính vs Tìm kiếm nhị phân trong python
Bijay Kumar
Python là một trong những ngôn ngữ phổ biến nhất ở Hoa Kỳ. Tôi đã làm việc với Python trong một thời gian dài và tôi có kinh nghiệm làm việc với nhiều thư viện khác nhau trên Tkinter, Pandas, NumPy, Turtle, Django, Matplotlib, Tensorflow, Scipy, Scikit-Learn, v.v… Tôi có kinh nghiệm làm việc với nhiều khách hàng khác nhau . Kiểm tra hồ sơ của tôi