พับวิธีการค้นหาครึ่ง :
ในตารางที่สั่งซื้อให้เปรียบเทียบค่าข้อมูลที่จะค้นหาด้วยค่าองค์ประกอบกลางของช่วงการค้นหาและจะมีสามสถานการณ์:
1) หากค่าข้อมูลที่จะพบจะเท่ากับค่าองค์ประกอบกลางให้ใส่ดัชนีของค่าองค์ประกอบกลางกลับมา
2) หากค่าข้อมูลที่จะค้นหามีขนาดเล็กกว่าค่าขององค์ประกอบกลางให้ใช้ครึ่งแรกของช่วงการค้นหาทั้งหมดเป็นช่วงการค้นหาใหม่และดำเนินการ 1) จนกว่าจะพบค่าที่เท่ากัน
3) หากค่าข้อมูลที่จะค้นหามีขนาดใหญ่กว่าค่าขององค์ประกอบกลางให้ใช้ครึ่งหลังของช่วงการค้นหาทั้งหมดเป็นช่วงการค้นหาใหม่และดำเนินการ 1) จนกว่าจะพบค่าที่เท่ากัน
4) หากไม่พบค่าเดียวกันในตอนท้ายข้อความแสดงข้อผิดพลาดจะถูกส่งคืน
ตามต้นไม้ไบนารีค่ากลางคือรากของต้นไม้ไบนารีครึ่งแรกคือทรีย่อยด้านซ้ายและครึ่งหลังเป็นทรีย่อยที่ถูกต้อง จำนวนการค้นหาวิธีการค้นหาครึ่งการค้นหาคือจำนวนเลเยอร์ที่ค่าอยู่ที่แน่นอน ภายใต้ความน่าจะเป็นที่เท่าเทียมกันโดยประมาณ
log2 (n+1) -1
การคัดลอกรหัสมีดังนี้:
// ข้อมูลคืออาร์เรย์ที่จะค้นหา X คือค่าข้อมูลที่จะค้นหา Beg เป็นจุดเริ่มต้นของช่วงการค้นหาและสุดท้ายคือช่วงท้ายของช่วงการค้นหา
// วิธีที่ไม่ซ้ำกัน
int bisearch (ข้อมูล int [], const int x, int beg, int สุดท้าย)
-
int mid; // ตำแหน่งกลาง
if (Beg> สุดท้าย)
-
กลับ -1;
-
ในขณะที่ (ขอ <= สุดท้าย)
-
mid = (ขอ + สุดท้าย) / 2;
ถ้า (x == ข้อมูล [กลาง])
-
กลับกลาง;
-
อื่นถ้า (ข้อมูล [mid] <x)
-
ขอ = กลาง + 1;
-
อื่นถ้า (ข้อมูล [mid]> x)
-
สุดท้าย = กลาง - 1;
-
-
กลับ -1;
-
// วิธีการเรียกซ้ำ
int iTerBisearch (ข้อมูล int [], const int x, int beg, int สุดท้าย)
-
int mid = -1;
mid = (ขอ + สุดท้าย) / 2;
ถ้า (x == ข้อมูล [กลาง])
-
กลับกลาง;
-
อื่นถ้า (x <data [mid])
-
ส่งคืน iterbisearch (data, x, beg, mid - 1);
-
อื่นถ้า (x> data [mid])
-
ส่งคืน iterbisearch (data, x, mid + 1, สุดท้าย);
-
กลับ -1;
-
// ฟังก์ชันหลัก
int _tmain (int argc, _tchar* argv [])
-
int data1 [60] = {0};
int no2Search = 45;
ศาล << "อาร์เรย์คือ:" << endl;
int siz = sizeof (data1)/sizeof (int);
สำหรับ (int i = 0; i <siz; i ++)
-
data1 [i] = i;
ศาล << data1 [i] << "";
-
ศาล << endl;
ดัชนี int = -1;
// index = bisearch (data1, no2Search, 0, siz);
index = iterBisearch (data1, no2Search, 0, siz);
ศาล << "ดัชนีของ" << no2Search << "คือ" << ดัชนี << endl;
getchar ();
กลับ 0;
-
การคัดลอกรหัสมีดังนี้:
-
* ครึ่งเพื่อค้นหาตำแหน่งของอักขระในอาร์เรย์ (รายการสั่งซื้อ)
* @param Array อาร์เรย์ที่ดึงมา
* @param x อักขระที่จะพบ
* @returns ตำแหน่งของตัวละครในอาร์เรย์ไม่พบผลตอบแทน -1
-
ฟังก์ชัน BinarySearch (Array, x) {
var lowpoint = 1;
var higpoint = array.length;
var returnValue = -1;
จุดกึ่งกลาง var;
พบ var = false;
ในขณะที่ ((lowpoint <= higpoint) && (พบ)) {
midpoint = math.ceil ((lowpoint+higpoint)/2);
//console.log(lowpoint+"===="+midpoint+"===="+higpoint);
if (x> array [midpoint-1]) {
lowpoint = midpoint+1;
-
อื่นถ้า (x <array [midpoint-1]) {
higpoint = midpoint-1;
-
อื่นถ้า (x = อาร์เรย์ [midpoint-1]) {
พบ = จริง;
-
-
ถ้า (พบ) {
returnValue = midpoint;
-
returnValue;
-
/*var array2 = [1,2,3,4,5,6,7,8,9,9,100,109];*/
var array2 = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
console.log (BinarySearch (array2, 'C'));