อัลกอริธึมการค้นหาแบบไบนารีเป็นอัลกอริธึมที่อิงตามกลไกการเปรียบเทียบและการแยก อัลกอริทึมการค้นหาแบบไบนารีเรียกอีกอย่างว่า การค้นหาครึ่งช่วง การค้นหาแบบลอการิทึม หรือไบนารีสับ . อัลกอริทึมการค้นหาไบนารี ค้นหาตำแหน่งของค่าเป้าหมายในอาร์เรย์ที่เรียงลำดับ จะเปรียบเทียบค่าเป้าหมายกับองค์ประกอบตรงกลางของอาร์เรย์ หากองค์ประกอบเท่ากับองค์ประกอบเป้าหมาย อัลกอริทึมจะส่งกลับดัชนี ของธาตุที่พบ และหากไม่เท่ากัน อัลกอริธึมการค้นหาจะใช้ครึ่งหนึ่งของอาร์เรย์นั้น โดยอิงจากการเปรียบเทียบค่า อัลกอริธึมใช้ครึ่งแรกอย่างใดอย่างหนึ่ง ( เมื่อค่าน้อยกว่าค่ากลาง ) และครึ่งหลัง ( เมื่อค่ามากกว่าค่ากลาง ) และทำเช่นเดียวกันสำหรับครึ่งอาร์เรย์ถัดไป
Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8 คำอธิบาย
สำหรับอาร์เรย์ของเรา -
เราจะเปรียบเทียบ 55 กับองค์ประกอบตรงกลางของอาร์เรย์ซึ่งก็คือ 18 ซึ่งน้อยกว่า 55 ดังนั้นเราจะใช้ครึ่งหลังของอาร์เรย์ เช่น อาร์เรย์ {24, 45, 55, 99} อีกครั้ง ค่ากลางคือ 55 ตรวจสอบค่าขององค์ประกอบการค้นหาด้วย และค่าที่ตรงกันแล้วเราจะคืนค่าดัชนีของค่านี้ด้วย 8
หากองค์ประกอบการค้นหามีขนาดเล็กกว่าตรงกลางมากกว่าที่เราจะใช้ครึ่งแรกและดำเนินต่อไปจนกว่าจะพบองค์ประกอบที่กึ่งกลางของอาร์เรย์
ในการดำเนินการค้นหาแบบไบนารี เราสามารถเขียนโค้ดได้สองวิธี สองวิธีนี้จะเลื่อนออกไปในลักษณะที่เราเรียกใช้ฟังก์ชันที่ตรวจสอบองค์ประกอบการค้นหาแบบไบนารีเท่านั้น คือ:
-
การใช้การวนซ้ำ − นี่หมายถึงการใช้ลูปภายในฟังก์ชันที่ตรวจสอบความเท่าเทียมกันขององค์ประกอบตรงกลาง
-
การใช้ ในวิธีนี้ ฟังก์ชันจะเรียกตัวเองซ้ำแล้วซ้ำอีกด้วยชุดค่าที่ต่างกัน
ตัวอย่าง
#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
int A[] = {0,12,6,12,12,18,34,45,55,99};
int n=55;
printf("%d is found at Index %d \n",n,iterativeBsearch(A,10,n));
return 0;
}
int iterativeBsearch(int A[], int size, int element) {
int start = 0;
int end = size-1;
while(start<=end) {
int mid = (start+end)/2;
if( A[mid] == element) {
return mid;
} else if( element < A[mid] ) {
end = mid-1;
} else {
start = mid+1;
}
}
return -1;
} ผลลัพธ์
55 is found at Index 8
ตัวอย่าง
#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
if(start>end) return -1;
int mid = (start+end)/2;
if( A[mid] == element ) return mid;
else if( element < A[mid] )
RecursiveBsearch(A, start, mid-1, element);
else
RecursiveBsearch(A, mid+1, end, element);
}
int main() {
int A[] = {0,2,6,11,12,18,34,45,55,99};
int n=55;
printf("%d is found at Index %d \n",n,RecursiveBsearch(A,0,9,n));
return 0;
} ผลลัพธ์
55 is found at Index 8
