двоичный поиск в массиве отличается от линейного тем, что массив до поиска должен быть отсортирован. После сортировки массив дробится пополам, средний элемент сравнивается с искомым значением. Если совпало, значит все, если нет - ищем в каком из двух подмассивов находится искомое значение. Переходим в нужный подмассив, который опять дробится и операция продолжается до совпадения искомого значения со средним элементом.
#include<stdlib.h>
#define SIZE 1000
int binarySearch(int[], int, int, int, int);
//void printRow(int[], int, int, int, int);
int determination(void);
int printing(int num, int Mass[]);
void shakerSort(void);
using namespace std;
int Array[SIZE] = {0};
int main()
{
int key, result;
determination();
printing(SIZE, Array);
shakerSort();
printf("\n\n\n");
printing(SIZE, Array);
printf("Введите искомое число\t");
scanf("%d", &key);
result = binarySearch(Array, key, 0, (SIZE - 1), SIZE);
//printf("res = %d", result);
if (result != -1)
{
printf("Искомое число находится на %d позиции\n\n\n", result);
}
else
{
printf("Результат отсутствует\n\n\n");
}
return 0;
}
int determination()//функция присвоения значений массиву
{
for (int i = 0; i < SIZE; i++)
{
Array [i] = rand() % (SIZE * 3);
}
}
int printing(int num, int Mass[])//вывод на экран одномерного массива
{
for (int i = 0; i < num; i++)
{
printf("%d\t%d\n", i , Mass[i]);
}
}
int binarySearch(int A[], int key, int low, int high, int size)
{
int middle;
while (low <= high)
{
middle = (low + high) / 2;
if (key == A [middle])
{
return middle;
}
else if (key < A[middle])
{
high = middle - 1;
}
else
{
low = middle + 1;
}
}
return -1;
}
void shakerSort() //сортировку массива производим известным способом
{
int tmp = 0, high = 0, low = (SIZE - 1);
while (high < low)
{
for (int i = high; i < low; i++)//двигаемся сверху вниз
{
if (Array[i] > Array[i + 1]) //если текущее значение больше
{
tmp = Array[i]; //следующего меняем их местами
Array[i] = Array[i + 1]; //(двигаем его вниз)
Array[i + 1] = tmp; //
}
}
low--;//обратите внимание, что нижняя граница поднимается
//вверх
for (int j = low; j > high; j--)//двигаемся снизу вверх
{
if (Array[j] < Array[j - 1]) //если текущее значение меньше
{
tmp = Array[j]; //следующего меняем их местами
Array[j] = Array[j - 1]; //(двигаем его вверх)
Array[j - 1] = tmp; //
}
}
high++;
}
}
Я забил в значение SIZE 1000 000. На процессоре q6600 алгоритм выполняется уже минут 20. При этом одно ядро постоянно загружено на 100%.
Если в массиве 10 000 элементов, то алгоритм выполняется за несколько секунд.