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

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

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

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
}