การค้นหาแบบไบนารี หรือที่เรียกว่าการค้นหาแบบครึ่งช่วง การค้นหาแบบลอการิทึม หรือไบนารีสับ เป็นอัลกอริธึมการค้นหาที่ค้นหาตำแหน่งของค่าเป้าหมายภายในอาร์เรย์ที่จัดเรียง การค้นหาแบบไบนารีจะเปรียบเทียบค่าเป้าหมายกับองค์ประกอบตรงกลางของอาร์เรย์ หากไม่เท่ากัน ครึ่งหนึ่งที่เป้าหมายไม่สามารถโกหกได้จะถูกตัดออก และการค้นหาจะดำเนินต่อไปในครึ่งที่เหลือ นำองค์ประกอบตรงกลางมาเปรียบเทียบกับค่าเป้าหมายอีกครั้ง และทำซ้ำจนกว่าจะพบค่าเป้าหมาย หากการค้นหาสิ้นสุดโดยเหลืออีกครึ่งหนึ่งว่างเปล่า เป้าหมายจะไม่อยู่ในอาร์เรย์ แม้ว่าแนวคิดจะเรียบง่าย แต่การใช้การค้นหาแบบไบนารีอย่างถูกต้องนั้นต้องการความใส่ใจในรายละเอียดปลีกย่อยบางประการเกี่ยวกับเงื่อนไขการออกและการคำนวณจุดกึ่งกลาง โดยเฉพาะอย่างยิ่งหากค่าในอาร์เรย์ไม่ใช่ตัวเลขทั้งหมดในช่วง
การค้นหาแบบไบนารีเป็นอัลกอริธึมการค้นหาที่ได้รับความนิยมมากที่สุด มีประสิทธิภาพและยังเป็นหนึ่งในเทคนิคที่ใช้กันมากที่สุดที่ใช้ในการแก้ปัญหา
หากชื่อทั้งหมดในโลกถูกเขียนเรียงตามลำดับและคุณต้องการค้นหาตำแหน่งของชื่อใดชื่อหนึ่ง การค้นหาแบบไบนารีจะทำสำเร็จในการทำซ้ำสูงสุด 35 ครั้ง
การค้นหาแบบไบนารีทำงานเฉพาะกับชุดขององค์ประกอบที่เรียงลำดับ หากต้องการใช้การค้นหาแบบไบนารีในคอลเล็กชัน จะต้องจัดเรียงคอลเล็กชันก่อน
เมื่อใช้การค้นหาแบบไบนารีเพื่อดำเนินการกับชุดที่จัดเรียง จำนวนการวนซ้ำจะลดลงตามค่าที่กำลังค้นหาเสมอ
ให้เราพิจารณาอาร์เรย์ต่อไปนี้ -
โดยใช้การค้นหาเชิงเส้น ตำแหน่งขององค์ประกอบ 8 จะถูกกำหนดในการทำซ้ำครั้งที่ 9
เรามาดูกันว่าสามารถลดจำนวนการวนซ้ำโดยใช้การค้นหาแบบไบนารีได้อย่างไร ก่อนที่เราจะเริ่มต้นการค้นหา เราจำเป็นต้องทราบจุดเริ่มต้นและจุดสิ้นสุดของช่วง เรียกว่าต่ำและสูง
Low = 0 High = n-1
ตอนนี้ เปรียบเทียบค่าการค้นหา K กับองค์ประกอบที่อยู่ตรงกลางของขอบเขตล่างและบน หากค่า K มากกว่า ให้เพิ่มขอบเขตล่าง มิฉะนั้นจะลดขอบเขตบน
จากภาพด้านบน ขอบล่างคือ 0 และขอบบนคือ9
ค่ามัธยฐานของขอบเขตล่างและบนคือ (lower_bound + upper_bound) / 2 =4 โดยที่ a[4] =4 ค่า 4>2 ซึ่งเป็นค่าที่คุณกำลังค้นหา ดังนั้น เราไม่จำเป็นต้องทำการค้นหาองค์ประกอบใดๆ ที่เกิน 4 เนื่องจากองค์ประกอบที่เกินจะมากกว่า 2 อย่างเห็นได้ชัด
ดังนั้นเราจึงสามารถวางขอบเขตบนของอาร์เรย์ไปยังตำแหน่งขององค์ประกอบ 4 ได้เสมอ ตอนนี้ เราทำตามขั้นตอนเดียวกันในอาร์เรย์เดียวกันด้วยค่าต่อไปนี้ -
Low: 0 High: 3
ทำซ้ำขั้นตอนนี้ซ้ำๆ จนกระทั่งต่ำ> สูง หากทำซ้ำใด ๆ เราได้รับ a[mid]=key เราจะคืนค่า mid นี่คือตำแหน่งของคีย์ในอาร์เรย์ หากไม่มีคีย์ในอาร์เรย์ เราจะคืนค่า -1
ตัวอย่าง
int binarySearch(int low,int high,int key){
while(low<=high){
int mid=(low+high)/2;
if(a[mid]<key){
low=mid+1;
}
else if(a[mid]>key){
high=mid-1;
}
else{
return mid;
}
}
return -1; //key not found
} 