Сложите метод получения половины :
В упорядоченной таблице сравните значение данных, которое будет выполнено, со значением промежуточного элемента диапазона поиска, и будет три ситуации:
1) Если найти значение данных, в точности равное значению промежуточного элемента, верните индекс значения промежуточного элемента.
2) Если поиск данных, подлежащее поиску, меньше значения промежуточного элемента, используйте первую половину всего диапазона поиска в качестве нового диапазона поиска, и выполнить 1) до тех пор, пока не будет найдено равное значение.
3) Если поиск данных, подлежащее поиску, больше, чем значение промежуточного элемента, используйте вторую половину всего диапазона поиска в качестве нового диапазона поиска, и выполнить 1) до тех пор, пока не будет найдено равное значение.
4) Если такое же значение не может быть найдено в конце, будет возвращено сообщение об ошибке.
Согласно бинарному дереву, среднее значение является корнем бинарного дерева, первая половина - левая поддерево, а вторая половина - правая поддерево. Количество поисков для метода поиска полуполучания-это точно количество слоев, где расположено значение. При равной вероятности, приблизительно
log2 (n+1) -1
Кода -копия выглядит следующим образом:
// Данные - это массив для поиска, x - это значение данных, которое нужно искать, Beg - это начало диапазона поиска, и последнее - конец диапазона поиска
// нерекурсивный метод
int bisearch (int data [], const int x, int beg, int last)
{
int mid; // средняя позиция
if (BEG> LAST)
{
возврат -1;
}
в то время как (BEG <= последний)
{
mid = (угадать + последнее) / 2;
if (x == data [mid])
{
вернуться в середину;
}
иначе if (data [mid] <x)
{
BEG = MID + 1;
}
иначе if (data [mid]> x)
{
Последний = середина - 1;
}
}
возврат -1;
}
// рекурсивный метод
int iterbisearch (int data [], const int x, int beg, int last)
{
int mid = -1;
mid = (угадать + последнее) / 2;
if (x == data [mid])
{
вернуться в середину;
}
иначе if (x <data [mid])
{
вернуть iterbisearch (data, x, beg, mid - 1);
}
иначе if (x> data [mid])
{
вернуть iterbisearch (data, x, mid + 1, last);
}
возврат -1;
}
// Основная функция
int _tmain (int argc, _tchar* argv [])
{
int data1 [60] = {0};
int no2search = 45;
cout << "Массив:" << endl;
int siz = sizeof (data1)/sizeof (int);
для (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 << "Индекс" << no2search << "is" << index << endl;
getChar ();
возврат 0;
}
Кода -копия выглядит следующим образом:
/**
* Половина, чтобы найти позицию символов в массиве (заказанный список)
* @param массив полученный массив
* @param x символы, которые можно найти
* @returns позиция персонажа в массиве, нет найденного возврата -1
*/
Функция BinarySearch (Array, x) {
var lowpoint = 1;
var higpoint = array.length;
var returnValue = -1;
var midpoint;
var обнаружил = false;
while ((lowpoint <= higpoint) && (! найдено)) {
midpoint = math.ceil ((низкая точка+higpoint)/2);
//console.log(lowpoint+"===="+midpoint+"===="+higpoint);
if (x> array [midpoint-1]) {
низкая точка = средняя точка+1;
}
иначе if (x <array [midpoint-1]) {
higpoint = midpoint-1;
}
иначе if (x = array [midpoint-1]) {
найдено = true;
}
}
if (найдено) {
returnValue = средняя точка;
}
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'));