Записки программиста Программирование и не только

Последовательный (линейный) поиск

Поиск последовательно проверяет все элементы, а так же достижение конца массива.

int line_seach(int *mArray, int _size, int find_el)
{
	int position = 0;
	for(;(mArray[position] != find_el) && (position < _size); position++);	//Поиск

	position++;	//Корректируем номер позиции

	return position <= _size ? position : 0;	//Если элемент найден, то возвращаем его позицию, если нет, то 0
}

Двоичный поиск (только для отсортированных массивов)

Массив делится пополам и граница сдвигается в соответствии с тем, где, возможно, находится искомый элемент.

Боевой пример:

int dv_seach(int *mArray, int _size, int find_el)
{
	int left = 0, right = _size - 1, m;	//Устанавливаем границы
	while(left < right)
	{
		m = (left + right) / 2;	//Выбираем середину
		if (find_el > mArray[m]) left = m + 1;	//Если элемент в середине рассматриваемого
												//участка больше искомого, то сдвигаем границу влево
		else right = m;							//Если меньше - вправо
	}

	return find_el == mArray[left] ? left + 1 : 0;	//Если элемент найден, то возвращаем его позицию, если нет, то 0
}

Поиск с барьером

Алгоритм поиска заключается в установке "барьера" - искомого элемента - в конец массива.
Таким образом пропадает необходимость проверки на достижение конца массива.

Боевой пример:

int barrier_seach(int *mArray, int _size, int find_el)
{
	int position = 0;
	if (mArray[_size-1] != find_el)	//Проверим, нет ли искомого элемента на последней позиции
	{
		mArray[_size-1] = find_el;	//Установим "барьер"
		for(;mArray[position] != find_el; position++);	//Поиск
		position++;	//Корректируем номер позиции
	}
	else return _size;	//Если искомый элемент на последней позиции, то возвращаем размер

	return position < _size ? position : 0;	//Если элемент найден, то возвращаем его позицию, если нет, то 0
}

КМП поиск (Алгоритм Кнута Морриса Пратта)

Разъяснения напишу позже.

int Find (string str, string templ)
{
	int  i, j, strlen, templlen;

	strlen = str.length();
	templlen = templ.length();
	int *d = new int[templlen];
	// Вычисление префикс-функции
	i = 0;
	j = -1;
	d[0] = -1;
	while (i < templlen-1)
	{
		while ((j >= 0) && (templ[j] != templ[i]))
			j = d[j];
		++i;
		++j;
		d[i] = (templ[i] == templ[j]) ? d[j] : j;
	}
	// Поиск строки
	for (i = 0, j = 0; (i < = strlen-1) && (j <= templlen-1); ++i,++j)
		while ((j >= 0) && (templ[j] != str[i]))
			j = d[j];
	delete[] d;
	// Если совпадение есть - возвращаем позицию,
	// если нет - -1
	return (j == templlen) ? i - j : -1;
}

Вызывается:

	Find(*str, *tmpl)

Где:

	string* str;	//строка, в которой ищем
	string* tmpl;	//строка, которую ищем

Алгоритм Бойера-Мура-Хорспула

Сортировка:
1. Быстрая сортировка (англ. quicksort)
2. Сортировка Шелла (англ. Shell sort)

Поиск:
1. Прямой поиск (он же Простой, он же Алгоритм грубой силы)

И новенькое:
Алгоритм Бойера-Мура-Хорспула

Прямой поиск

И вновь алгоритмы. Тут уже есть:
1. Быстрая сортировка (англ. quicksort)
2. Сортировка Шелла (англ. Shell sort)

Добавим алгоритмов поиска. Итак:

Прямой поиск.