Linear Search เป็นเทคนิคการค้นหาเพื่อค้นหาค่าเฉพาะจาก Array นี่คือเทคนิคค้นหาที่ง่ายที่สุด
ในเทคนิคค้นหานี้
ค่าที่ต้องการค้นหาจะถูกเปรียบเทียบกับทุกองค์ประกอบใน Array
หากพบค่า Index ขององค์ประกอบจะถูกคืนค่า
หากองค์ประกอบเฉพาะนั้นไม่มีอยู่ทั่ว Array ให้คืนค่า -1 หรือข้อความที่เกี่ยวข้อง
Pseudocode
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
Time Complexity
Time Complexity แย่ที่สุดของ Linear Search คือ O(n) กรณีแย่ที่สุดเกิดเมื่อองค์ประกอบอยู่ที่ Index สุดท้าย หรือไม่มีอยู่เลย
Time Complexity ดีที่สุดคือ O(1) เกิดเมื่อองค์ประกอบอยู่ที่ Index แรก
Improved Linear Search
Time Complexity แย่ที่สุดของ Linear Search สามารถปรับปรุงเป็น O(n/2) ได้ โดยใช้ Two Pointers คือ Left และ Right และทำการเปรียบเทียบ 2 ครั้งพร้อมกัน ลด Complexity แย่ที่สุดเหลือ 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
ในตัวอย่างข้างต้น องค์ประกอบที่อยู่ Index สุดท้าย ถูกพบในรอบแรกเอง หากใช้วิธีแรก จะใช้ 10 รอบ
หากไม่พบองค์ประกอบ Complexity แย่ที่สุดคือ O(n/2) เนื่องจากจำนวนรอบรวมเป็น n/2 ในวิธีที่สอง
Linear Search มีประโยชน์แค่ไหน?
Linear Search นادرًا ما ใช้ เพราะมีอัลกอริทึมค้นหาที่ดีกว่า เช่น Binary Search ที่ให้ Time Complexity ดีกว่า Linear Search ไม่มีประสิทธิภาพสำหรับ Array ขนาดใหญ่
