การค้นหาเชิงเส้นเป็นเทคนิคการค้นหาเพื่อค้นหาค่าบางค่าจากอาร์เรย์ นี่เป็นเทคนิคการค้นหาที่ง่ายที่สุด
ในเทคนิคการค้นหานี้
-
ค่าที่จะค้นหาจะถูกเปรียบเทียบกับองค์ประกอบทั้งหมดในอาร์เรย์
-
หากพบค่า ดัชนีขององค์ประกอบจะถูกส่งคืน
-
หากไม่มีองค์ประกอบเฉพาะในอาร์เรย์ ให้ส่งคืน -1 หรือข้อความสตริงที่เกี่ยวข้อง
รหัสเทียม
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
ตัวอย่าง
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) ผลลัพธ์
Element present at index 4
ความซับซ้อนของเวลา
ความซับซ้อนของเวลากรณีที่เลวร้ายที่สุดของการค้นหาเชิงเส้นคือ O(n) กรณีที่เลวร้ายที่สุดเกิดขึ้นเมื่อองค์ประกอบอยู่ที่ดัชนีสุดท้ายของอาร์เรย์หรือไม่ปรากฏเลย
ความซับซ้อนของเวลากรณีและปัญหาที่ดีที่สุดของการค้นหาเชิงเส้นคือ O(1) กรณีที่ดีที่สุดเกิดขึ้นเมื่อองค์ประกอบอยู่ที่ดัชนีแรกของอาร์เรย์
ปรับปรุงการค้นหาเชิงเส้น
ความซับซ้อนของกรณีที่เลวร้ายที่สุดของการค้นหาเชิงเส้นสามารถปรับปรุงเป็น O(n/2) ซึ่งสามารถทำได้โดยใช้ตัวชี้สองตัว ซ้ายและขวา และเปรียบเทียบพร้อมกันสองครั้ง ดังนั้นจึงลดความซับซ้อนของเวลากรณีที่เลวร้ายที่สุดของการค้นหาเชิงเส้นเป็น O(n/2)
ตัวอย่าง
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) ผลลัพธ์
Element present at index 9
ในตัวอย่างข้างต้น พบองค์ประกอบที่ดัชนีสุดท้าย ในการวนซ้ำครั้งแรกเอง การใช้วิธีแรกจะต้องทำซ้ำ 10 ครั้งจึงจะพบองค์ประกอบนี้
หากไม่พบองค์ประกอบ ความซับซ้อนของกรณีที่เลวร้ายที่สุดคือ O(n/2) เนื่องจากจำนวนการวนซ้ำทั้งหมดเป็น n/2 ในวิธีที่สอง
การค้นหาเชิงเส้นมีประโยชน์อย่างไร
การค้นหาเชิงเส้นมักไม่ค่อยใช้ เนื่องจากมีอัลกอริธึมการค้นหาที่ดีกว่า เช่น การค้นหาแบบไบนารี ซึ่งให้เวลาที่ซับซ้อนกว่า การค้นหาเชิงเส้นไม่มีประสิทธิภาพสำหรับอาร์เรย์อินพุตขนาดใหญ่
