Tìm kiếm tuyến tính là một kỹ thuật tìm kiếm để tìm kiếm một số giá trị cụ thể từ một mảng. Đây là kỹ thuật tìm kiếm đơn giản nhất.
Trong kỹ thuật tìm kiếm này,
-
giá trị được tìm kiếm được so sánh với tất cả các phần tử trong mảng.
-
Nếu giá trị được tìm thấy, chỉ mục của phần tử sẽ được trả về.
-
Nếu phần tử cụ thể không có trong mảng, thì trả về -1 hoặc một số thông báo chuỗi có liên quan.
Mã giả
linearSearch(int array[], int value): for i=0 to len(array): if(array[i]==value): Element is Present //outside for loop Element Not Present // element not found in the whole array
Ví dụ
def linearSearch(arr,value):
for i in range(len(arr)):
if(arr[i]==value):
return i
return -1
array=[1,2,3,4,5,6,7,8,9,10]
value=5
a=linearSearch(array,value)
if(a==-1):
print("Element not present")
else:
print("Element present at index",a) Đầu ra
Element present at index 4
Độ phức tạp về thời gian
Độ phức tạp thời gian trong trường hợp xấu nhất của tìm kiếm tuyến tính là O (n). Trường hợp xấu nhất xảy ra khi phần tử có ở chỉ mục cuối cùng của mảng hoặc không có ở tất cả.
Độ phức tạp thời gian tốt nhất của tìm kiếm tuyến tính là O (1). Trường hợp tốt nhất xảy ra khi phần tử có mặt ở chỉ mục đầu tiên của mảng.
Tìm kiếm tuyến tính được cải thiện
Độ phức tạp trong trường hợp xấu nhất của tìm kiếm tuyến tính có thể được cải thiện thành O (n / 2). Điều này có thể được thực hiện bằng cách sử dụng hai con trỏ, trái và phải và thực hiện hai phép so sánh cùng một lúc, do đó giảm độ phức tạp thời gian trong trường hợp xấu nhất của tìm kiếm tuyến tính xuống O (n / 2).
Ví dụ
def linearSearch(arr,value):
left=0
right=len(arr)-1
while(left<=right):
if(arr[left]==value):
return left
elif(arr[right]==value):
return right
left+=1
right-=1
return -1
array=[1,2,3,4,5,6,7,8,9,10]
value=10
a=linearSearch(array,value)
if(a==-1):
print("Element not present")
else:
print("Element present at index",a) Đầu ra
Element present at index 9
Trong ví dụ trên, phần tử hiện diện ở chỉ mục cuối cùng, được tìm thấy trong chính lần lặp đầu tiên. Sử dụng phương pháp đầu tiên, sẽ mất 10 lần lặp để tìm phần tử này.
Nếu phần tử không được tìm thấy, độ phức tạp trong trường hợp xấu nhất là O (n / 2), vì tổng số lần lặp là n / 2 trong phương thức thứ hai.
Tìm kiếm tuyến tính hữu ích như thế nào?
Tìm kiếm tuyến tính hiếm khi được sử dụng vì có các thuật toán tìm kiếm tốt hơn như tìm kiếm nhị phân cung cấp độ phức tạp về thời gian tốt hơn. Tìm kiếm tuyến tính không hiệu quả đối với mảng đầu vào lớn.