home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

Binary Search: การค้นหาแบ่งครึ่ง

คืออะไร?

Binary Search ใช้กับ Sorted List** แบ่งรายการเป็น 2 ส่วนย่อย ตรงกลาง = Key → คืนตำแหน่ง มิฉะนั้น ไปซ้ายหรือขวา ทำซ้ำจนเจอหรือเกิน Range

Complexity

  • Time: Best O(1), Average/Worst O(log₂ n)
  • Space: O(1)

Input/Output

Input:  Sorted: 12 25 48 52 67 79 88 93  Key: 79
Output: Item found at location: 5

อัลกอริทึม

binarySearch(array, start, end, key):
  if start <= end:
    mid = start + (end - start) / 2
    if array[mid] == key: return mid
    if array[mid] > key:  return binarySearch(array, start, mid-1, key)
    else:                 return binarySearch(array, mid+1, end, key)
  else: return invalid

โค้ด C++ และ Output

// binarySearch recursive function
// main: input n, array, searchKey
Enter number of items: 8
Enter items: 12 25 48 52 67 79 88 93
Enter search key: 79
Item found at location: 5