ค้นหาไบนารีใน C++

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

วิธีนี้ทำได้โดยเริ่มจากอาร์เรย์ทั้งหมด จากนั้นจะลดลงครึ่งหนึ่ง หากค่าข้อมูลที่ต้องการมากกว่าองค์ประกอบที่อยู่ตรงกลางอาร์เรย์ จะพิจารณาครึ่งบนของอาร์เรย์ มิฉะนั้นจะถือว่าครึ่งล่าง สิ่งนี้ทำอย่างต่อเนื่องจนกว่าจะได้ค่าข้อมูลที่ต้องการหรืออาร์เรย์ที่เหลือว่างเปล่า

โปรแกรมที่แสดงการค้นหาไบนารีใน C ++ แสดงไว้ด้านล่าง

ตัวอย่าง

#include
using namespace std;
int binarySearch(int arr[], int p, int r, int num) {
   if (p <= r) {
      int mid = (p + r)/2;
      if (arr[mid] == num)
         return mid ;
      if (arr[mid] > num)
         return binarySearch(arr, p, mid-1, num);
      if (arr[mid] < num)
         return binarySearch(arr, mid+1, r, num);
   }
   return -1;
}
int main(void) {
   int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int num;
   cout << "Enter the number to search: \n";
   cin >> num;
   int index = binarySearch (arr, 0, n-1, num);
   if(index == -1){
      cout<< num <<" is not present in the array";
   }else{
      cout<< num <<" is present at index "<< index <<" in the array";
   }
   return 0;
}

ผลลัพธ์

Enter the numberto search
20
20 is present at index 5 in the array

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

int binarySearch(int arr[], int p, int r, int num)

จากนั้นจะคำนวณจุดกึ่งกลางของอาร์เรย์ หากค่าที่จุดกึ่งกลางเท่ากับ num ค่านั้นจะถูกส่งกลับ หากค่ามากกว่า num อาร์เรย์จะเรียกตัวเองซ้ำด้วยขอบเขตล่าง p และขอบเขตบนตอนกลาง -1 หากค่าน้อยกว่า num อาร์เรย์จะเรียกตัวเองซ้ำด้วยขอบเขตล่าง mid+1 และขอบเขตบน r สามารถดูได้จากข้อมูลโค้ดต่อไปนี้

int binarySearch(int arr[], int p, int r, int num) {
   if (p <= r) {
      int mid = (p + r)/2;
      if (arr[mid] == num)
         return mid ;
      if (arr[mid] > num)
         return binarySearch(arr, p, mid-1, num);
      if (arr[mid] < num)
         return binarySearch(arr, mid+1, r, num);
   }
   return -1;
}

ในฟังก์ชัน main() จะมีการกำหนดอาร์เรย์ arr[] ขนาดของอาร์เรย์ถูกคำนวณและระบุจำนวนที่จะพบ จากนั้น binarySearch() จะถูกเรียกเพื่อค้นหาดัชนีของตัวเลข หากค่าที่ส่งคืนโดย binarySearch() คือ -1 แสดงว่าตัวเลขนั้นไม่อยู่ในอาร์เรย์ มิฉะนั้น ค่าดัชนีจะถูกส่งกลับ ด้านล่างนี้

int main(void) {
   int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int num = 33;
   int index = binarySearch (arr, 0, n-1, num);
   if(index == -1)
      cout<< num <<" is not present in the array";
   else
      cout<< num <<" is present at index "<< index <<" in the array";
   return 0;
}