binary_sort

Аватар пользователя merkul40
вс, 12/24/2017 - 23:17 -- merkul40

двоичный поиск в массиве отличается от линейного тем, что массив до поиска должен быть отсортирован. После сортировки массив дробится пополам, средний элемент сравнивается с искомым значением. Если совпало, значит все, если нет - ищем в каком из двух подмассивов находится искомое значение. Переходим в нужный подмассив, который опять дробится и операция продолжается до совпадения искомого значения со средним элементом. 

#include<stdio.h>   
#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 элементов, то алгоритм выполняется за несколько секунд.