Lipat metode setengah pencarian :
Dalam tabel yang dipesan, bandingkan nilai data yang akan dicari dengan nilai elemen menengah dari rentang pencarian, dan akan ada tiga situasi:
1) Jika nilai data yang dapat ditemukan persis sama dengan nilai elemen menengah, kembalikan indeks nilai elemen menengah.
2) Jika nilai data yang akan dicari lebih kecil dari nilai elemen perantara, gunakan paruh pertama dari seluruh rentang pencarian sebagai rentang pencarian baru, dan jalankan 1) sampai nilai yang sama ditemukan.
3) Jika nilai data yang akan dicari lebih besar dari nilai elemen perantara, gunakan paruh kedua dari seluruh rentang pencarian sebagai rentang pencarian baru, dan jalankan 1) sampai nilai yang sama ditemukan.
4) Jika nilai yang sama tidak dapat ditemukan pada akhirnya, pesan kesalahan akan dikembalikan.
Menurut pohon biner, nilai tengah adalah akar dari pohon biner, babak pertama adalah subtree kiri, dan babak kedua adalah subtree kanan. Jumlah pencarian untuk metode pencarian setengah pencarian adalah persis jumlah lapisan di mana nilainya berada. Di bawah probabilitas yang sama, kira -kira
log2 (n+1) -1
Salinan kode adalah sebagai berikut:
// Data adalah array yang akan dicari, x adalah nilai data yang akan dicari, BEG adalah awal dari rentang pencarian, dan yang terakhir adalah akhir dari rentang pencarian
// Metode non-rekursif
int bisearch (int data [], const int x, int beg, int last)
{
int mid; // posisi tengah
if (mohon> last)
{
kembali -1;
}
while (mohon <= terakhir)
{
mid = (beg + last) / 2;
if (x == data [mid])
{
kembali pertengahan;
}
lain jika (data [mid] <x)
{
Beg = mid + 1;
}
lain jika (data [mid]> x)
{
terakhir = mid - 1;
}
}
kembali -1;
}
// metode rekursif
int iterbisearch (int data [], const int x, int beg, int last)
{
int mid = -1;
mid = (beg + last) / 2;
if (x == data [mid])
{
kembali pertengahan;
}
lain jika (x <data [mid])
{
return iterbisearch (data, x, mohon, pertengahan - 1);
}
lain jika (x> data [mid])
{
return iterbisearch (data, x, mid + 1, terakhir);
}
kembali -1;
}
// fungsi utama
int _tmain (int argc, _tchar* argv [])
{
int data1 [60] = {0};
int no2search = 45;
cout << "Array adalah:" << endl;
int siz = sizeof (data1)/sizeof (int);
untuk (int i = 0; i <siz; i ++)
{
data1 [i] = i;
cout << data1 [i] << "";
}
cout << endl;
int index = -1;
// index = bisearch (data1, no2search, 0, siz);
index = iterbisearch (data1, no2search, 0, siz);
cout << "indeks" << no2search << "adalah" << indeks << endl;
getchar ();
kembali 0;
}
Salinan kode adalah sebagai berikut:
/**
* Setengah untuk menemukan posisi karakter dalam array (daftar yang dipesan)
* @param array array yang diambil
* @param x karakter dapat ditemukan
* @Kembalinya posisi karakter dalam array, tidak ada pengembalian -1 yang ditemukan -1
*/
Function BinarySearch (array, x) {
var lowpoint = 1;
var higpoint = array.length;
var returnValue = -1;
var titik tengah;
var found = false;
while ((lowpoint <= higpoint) && (! ditemukan)) {
midpoint = math.ceil ((lowpoint+higpoint)/2);
//console.log(lowpoint+"===="+MidPoint+"===="+HigPoint);
if (x> array [midpoint-1]) {
lowpoint = titik tengah+1;
}
lain if (x <array [midpoint-1]) {
higpoint = midpoint-1;
}
lain jika (x = array [midpoint-1]) {
ditemukan = true;
}
}
if (found) {
returnValue = titik tengah;
}
Return ReturnValue;
}
/*var array2 = [1,2,3,4,5,6,7,8,9,100,109];*/
var array2 = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
Console.log (BinarySearch (Array2, 'C'));