อธิบายการค้นหาไบนารีใน Python

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

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

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

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

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

เราจะเริ่มค้นหาด้วยดัชนีด้านซ้าย 0 และดัชนีด้านขวาเท่ากับดัชนีสุดท้ายของอาร์เรย์ ดัชนีองค์ประกอบกลาง (กลาง) คำนวณซึ่งเป็นผลรวมของดัชนีซ้ายและขวาหารด้วย 2 หากองค์ประกอบที่ต้องการน้อยกว่าองค์ประกอบกลาง ดัชนีด้านขวาจะเปลี่ยนเป็นระดับกลาง -1 ซึ่งหมายความว่าเราจะตอนนี้ จะดูเฉพาะครึ่งแรกของอาร์เรย์เท่านั้น ในทำนองเดียวกัน หากองค์ประกอบที่ต้องการมากกว่าองค์ประกอบตรงกลาง ดัชนีด้านซ้ายจะเปลี่ยนเป็น mid+1 ซึ่งหมายความว่าตอนนี้เราจะดูเฉพาะช่วงครึ่งหลังของอาร์เรย์เท่านั้น เราจะทำซ้ำขั้นตอนข้างต้นสำหรับครึ่งอาร์เรย์ที่เลือก

เราจะทราบได้อย่างไรว่าองค์ประกอบไม่มีอยู่ในอาร์เรย์

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

ตัวอย่าง

ให้เราใช้ sorted array ต่อไปนี้และเราต้องค้นหาองค์ประกอบ 6

L=0 H=8 กลาง=4

6<10 เพราะฉะนั้น ครึ่งแรกเลย

H=กลาง-1

L=0 H=3 กลาง=1

6>5 เพราะฉะนั้น เลือกครึ่งหลัง

L=กลาง+1

L=2 H=3 กลาง=2

6==6 พบองค์ประกอบ

ดังนั้นพบองค์ประกอบ 6 ที่ดัชนี 2

การนำไปใช้

จากอาร์เรย์ที่จัดเรียงที่กำหนด ให้ค้นหาองค์ประกอบที่ต้องการและพิมพ์ดัชนีขององค์ประกอบนั้นหากองค์ประกอบนั้นอยู่ในอาร์เรย์ หากไม่มีองค์ประกอบ ให้พิมพ์ -1

รหัสสำหรับการดำเนินการค้นหาแบบไบนารีแสดงไว้ด้านล่าง

ตัวอย่าง

def binary_search(arr,x):
   l=0
   r=len(arr)-1
   while(l<=r):
      mid=(l+r)//2
      if(arr[mid]==x):
         return mid
      elif(x<arr[mid]):
         r=mid-1
      elif(x>arr[mid]):
         l=mid+1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

ผลลัพธ์

6
-1

องค์ประกอบ 7 มีอยู่ที่ดัชนี 6

ไม่มีองค์ประกอบ 15 ในอาร์เรย์ ดังนั้น -1 จึงถูกพิมพ์