Home Algorithm อัลกอริทึ่ม : Linear Search VS Binary Search

อัลกอริทึ่ม : Linear Search VS Binary Search

by prtha112

ตอนนี้นะครับผมจะมาลองเทียบ การเขียนโปรเเกรมเเบบ ธรรมดา เทียบ กับการใช้ Binary Search เข้ามาช่วยเพิ่มประสิทธิภาพในการค้นหา
ยกตัวอย่าง : linear search

def linear(ar, target):
   for i in range(len(ar)):
      if i == target:
         print('Work')
         break

data = [55, 68, 77, 999, 1201, 2456]
linear(data, 1201)

จากภาพด้านบนนี่คือผมยกตัวอย่าง การค้นหาข้อมูลเเบบทั่วไป Linear Search นะครับ จะเห็นได้ว่ามีการวนลูบเพื่อค้นหาข้อมูล ทุก ตำเเหน่ง จน ถึงตำเเหน่งที่มีค่าตรงกับ Target ค่อยหยุด ถ้าเป็นเเบบนี้เนี่ยเวลามีข้อมูลมากๆ โปรเเกรมของเราก็จะยิ่งใช้เวลาในการประมวลผลมาขึ้นเรื่อยๆครับ

ต่อไปเป็น Binary search กระบวนการทำงานของมันจะเป็นลักษณะนี้

Target = 1201
[55, 68, 77, 999, 1201, 2456]
1. low=0, high = 5
2. middle = (low+5)/2
3. middle = 3
4. เทียบ 3 กับ 1201 จะได้ 999 < 1201 ให้เลื่อน Middle มาขวา
5. จะได้ Middle ใหม่ 4 ให้ทำการ (middle+high)/2 จะได้ 4.5
6. พบ 1201 ในตำเเหน่งที่ 4

จะเห็นได้ว่ามันทำงานเพียง 2 สเต็บเท่านั้นเอง เมื่อเทียบกับ linear ที่ทำงานถึง 5 สเต็บ กว่าจะพบ Target ส่วนตัวอย่างโค้ดนั้นค้นอากู๊เลยจ้า

Related Posts

Leave a Comment