ការស្វែងរកជាគោលពីរ
ក្បួនដោះស្រាយប្រកបដោយប្រសិទ្ធភាពសម្រាប់ស្វែងរកធាតុពីបញ្ជីដែលបានតម្រៀប។ វាដំណើរការដោយបែងចែកជាពីរម្ដងហើយម្ដងទៀតនូវផ្នែកនៃបញ្ជីដែលអាចមានធាតុនោះ។
Visualization
Details
Analogy
นี่เหมือนกับการค้นหาชื่อในสมุดโทรศัพท์។ คุณเปิดไปที่ตรงกลาง។ หากชื่อที่คุณกำลังค้นหามาตามตัวอักษรก่อนชื่อในหน้านั้น คุณจะรู้ว่าต้องเน้นไปที่ครึ่งแรก។ คุณทำซ้ำขั้นตอนนี้ โดยลดพื้นที่การค้นหาของคุณลงครึ่งหนึ่งในแต่ละครั้ง จนกว่าคุณจะระบุชื่อได้។
Purpose
ដើម្បីស្វែងរកตำแหน่งของค่าเป้าหมายอย่างรวดเร็วภายในอาร์เรย์ที่เรียงลำดับ។
Use Cases
พบบ่อยมากในการเขียนโปรแกรม။ ใช้ในเครื่องมือค้นหา การจัดทำดัชนีฐานข้อมูล และแอปพลิเคชันใดๆ ที่ต้องการการค้นหาที่รวดเร็วบนชุดข้อมูลขนาดใหญ่ที่เรียงลำดับ។
Algorithm Steps
left = 0, right = n-1
while left <= right:
mid = (left + right) / 2
if arr[mid] == target:
return mid
else if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 (not found)
Explanation
What's Happening?
ចាប់ផ្តើមស្វែងរកគោលដៅ 17 ក្នុងជួរពេញលេញ [0, 9]។
Code Implementation
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1