โครงสร้างข้อมูลและอัลกอริทึมการค้นหาแบบไบนารี

การค้นหาแบบไบนารีเป็นอัลกอริธึมการค้นหาที่รวดเร็วโดยมีความซับซ้อนรันไทม์ของΟ (log n) อัลกอริทึมการค้นหานี้ทำงานบนหลักการของการแบ่งและพิชิต เพื่อให้อัลกอริทึมนี้ทำงานได้อย่างถูกต้องการรวบรวมข้อมูลควรอยู่ในรูปแบบที่เรียงลำดับ

การค้นหาแบบไบนารีจะค้นหารายการใดรายการหนึ่งโดยการเปรียบเทียบรายการที่อยู่ตรงกลางส่วนใหญ่ของคอลเลกชัน หากการแข่งขันเกิดขึ้นดัชนีของสินค้าจะถูกส่งกลับ ถ้ารายการกลางมากกว่ารายการระบบจะค้นหารายการในอาร์เรย์ย่อยทางด้านซ้ายของรายการกลาง มิฉะนั้นรายการจะถูกค้นหาในอาร์เรย์ย่อยทางด้านขวาของรายการกลาง กระบวนการนี้จะดำเนินต่อไปในอาร์เรย์ย่อยเช่นกันจนกว่าขนาดของ subarray จะลดลงเป็นศูนย์

การค้นหาแบบไบนารีทำงานอย่างไร

เพื่อให้การค้นหาไบนารีทำงานได้จำเป็นต้องจัดเรียงอาร์เรย์เป้าหมาย เราจะเรียนรู้กระบวนการค้นหาไบนารีด้วยตัวอย่างภาพ ต่อไปนี้คืออาร์เรย์ที่จัดเรียงของเราและให้เราสมมติว่าเราต้องค้นหาตำแหน่งของค่า 31 โดยใช้การค้นหาแบบไบนารี

ขั้นแรกเราจะกำหนดครึ่งหนึ่งของอาร์เรย์โดยใช้สูตรนี้ -

mid = low + (high - low) / 2

นี่คือ 0 + (9 - 0) / 2 = 4 (ค่าจำนวนเต็ม 4.5) ดังนั้น 4 คือตรงกลางของอาร์เรย์

ตอนนี้เราเปรียบเทียบค่าที่เก็บไว้ที่ตำแหน่ง 4 โดยค่าที่กำลังค้นหาคือ 31 เราพบว่าค่าที่ตำแหน่ง 4 คือ 27 ซึ่งไม่ตรงกัน เนื่องจากค่ามีค่ามากกว่า 27 และเรามีอาร์เรย์ที่เรียงลำดับดังนั้นเราจึงรู้ด้วยว่าค่าเป้าหมายต้องอยู่ในส่วนบนของอาร์เรย์

เราเปลี่ยนค่าต่ำเป็นค่ากลาง + 1 และค้นหาค่ากลางใหม่อีกครั้ง

low = mid + 1
mid = low + (high - low) / 2

กลางใหม่ของเราคือ 7 ตอนนี้ เราเปรียบเทียบค่าที่เก็บไว้ที่ตำแหน่ง 7 กับค่าเป้าหมาย 31

ค่าที่เก็บไว้ที่ตำแหน่ง 7 ไม่ตรงกัน แต่เป็นมากกว่าสิ่งที่เรากำลังมองหา ดังนั้นค่าจะต้องอยู่ที่ส่วนล่างจากตำแหน่งนี้

ดังนั้นเราจึงคำนวณค่ากลางอีกครั้ง คราวนี้เป็น 5

เราเปรียบเทียบค่าที่เก็บไว้ที่ตำแหน่ง 5 กับมูลค่าเป้าหมายของเรา เราพบว่ามันตรงกัน

เราสรุปได้ว่าค่าเป้าหมาย 31 ถูกเก็บไว้ที่ตำแหน่ง 5

การค้นหาแบบไบนารีจะลดจำนวนรายการที่ค้นหาได้ลงครึ่งหนึ่งและลดจำนวนการเปรียบเทียบที่จะทำให้มีจำนวนน้อยลงมาก

รหัสเทียม

รหัสเทียมของอัลกอริทึมการค้นหาแบบไบนารีควรมีลักษณะดังนี้ -

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการค้นหาไบนารีใช้อาร์เรย์ในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่