ค้นหาไบนารี

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

ความซับซ้อนของเทคนิคการค้นหาแบบไบนารี

• ความซับซ้อนของเวลา : O(1) สำหรับกรณีที่ดีที่สุด O(log2 n) สำหรับกรณีทั่วไปหรือแย่ที่สุด
• ความซับซ้อนของอวกาศ: O(1)

อินพุตและเอาต์พุต

Input: 
A sorted list of data: 12 25 48 52 67 79 88 93
The search key 79
Output:
Item found at location: 5

อัลกอริทึม

binarySearch(array, start, end, key)

ป้อนข้อมูล - อาร์เรย์ที่จัดเรียง ตำแหน่งเริ่มต้นและสิ้นสุด และแป้นค้นหา

ผลลัพธ์ − ตำแหน่งของกุญแจ (หากพบ) มิฉะนั้น ตำแหน่งที่ไม่ถูกต้อง

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

ตัวอย่าง

#include<iostream>
using namespace std;

int binarySearch(int array[], int start, int end, int key) {
   if(start <= end) {
      int mid = (start + (end - start) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;

   int arr[n]; //create an array of size n
   cout << "Enter items: " << endl;

   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }

   cout << "Enter search key to search in the list: ";
   cin >> searchKey;

   if((loc = binarySearch(arr, 0, n, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

ผลลัพธ์

Enter number of items: 8
Enter items:
12 25 48 52 67 79 88 93
Enter search key to search in the list: 79
Item found at location: 5