Алгоритм поиска. Название

[MAKEDON]

Вопрос чисто теоретический. Я никак не могу вспомнить название алгоритма. Смысл просто. Нам в массиве чисел нужно найти определенный элемент. Вот алгоритм. Находим центр массива. Если этот элемент меньше, то рассматриваем уже только элементы справа от него, если больше то слева. Ну а если равен, то все. И так делаем пока найдем этот элемент. Как называется этот алгоритм? Он используется не только в программирование, кстати. Вот функция работающая по этому алгоритму.

int qs(int *mas,int size,int n){
	int middle,right=size-1,left=0;
	while(left<=right){
		middle=(right+left)/2+1;
		if(left==right){
			if(mas[middle]==n){return middle;}
			else{return -1;}
		}else{
			if(mas[middle]>n){right=middle;}
			if(mas[middle]<n){left=middle;}
		}
	}
	return -1;
}

[Sazary]

Бинарный поиск?

[MAKEDON]

Вряд ли. Там в названии всего этого процесса была буква Х. Я в гугле поискал, но так пока ничег не нашел. Там только алгоритм хемминга, хафмана.

[Sazary]

http://ru.wikipedia.org/wiki/Двоичный_поиск
http://algolist.manual.ru/search/bin_search.php

По описанию и приведенному вами примеру - вылитый он.

[MAKEDON]

ВОТ! Точно дихотомия. Ну буква х в нем есть Спасибо огромное! Не знал, что он так называется.

[Sazary]

Да уж, буква 'х' действительно есть ))

[Nomlpppp]

Судя по названию функции "qs" скорее всего quick sort - быстрая сортировка. Работает по методу Шелла. Действительно работает по принципу разбиения массива на части. За опорный может ьраться и из середины. Может об нем речь?

[Sazary]

Nomlpppp, да не, это обычный двоичный поиск )

[MAKEDON]

qs, это первое название, пришедшее ко мне в голову.

Кстати, на счет самой реализации. Она криво работает. Посмотрите:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void sort_vib(int *mas,int size);
int qs(int *mas,int size,int n);

int main(){
	int i,a[100],n,ch;
	srand(time(0));
	scanf("%d %d",&n,&ch);
	for(i=0;i<n;i++){
		a[i]=rand()%10;
	}
	for(i=0;i<n;i++){
		printf("%5d",a[i]);
	}
	printf("\n");
	sort_vib(a,n);
	printf("\n%d\n",qs(a,n,ch));
	return 0;
}

int qs(int *mas,int size,int n){
	int middle,right=size-1,left=0;
	while(left<=right){
		middle=(right+left)/2+1;
		if(left==right){
			if(mas[middle]==n){return middle;}
			else{return -1;}
		}else{
			if(mas[middle]>n){right=middle-1;}
			if(mas[middle]<n){left=middle+1;}
		}
	}
	return -1;
}

void sort_vib(int *mas,int size){
	int i,j,max,maxc=0,tmp;
	for(i=size-1;i>0;i--){
		max=mas[0];
		maxc=0;
		for(j=0;j<=i;j++){
			if(mas[j]>max){
				maxc=j;
				max=mas[j];
			}
		}
		tmp=mas[i];
		mas[i]=mas[maxc];
		mas[maxc]=tmp;
	}
	for(i=0;i<size;i++){
		printf("%5d",mas[i]);
	}
	return;
}

[MAKEDON]

Вот немного переделал. Но все равно некоторые варианты не ищет. В чем проблема?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void sort_vib(int *mas,int size);
int qs(int *mas,int size,int n);

int main(){
	int i,a[100],n,ch;
	srand(time(0));
	scanf("%d %d",&n,&ch);
	for(i=0;i<n;i++){
		a[i]=rand()%100;
	}
	for(i=0;i<n;i++){
		printf("%5d",a[i]);
	}
	printf("\n");
	sort_vib(a,n);
	printf("\n%d\n",qs(a,n,ch));
	return 0;
}

int qs(int *mas,int size,int n){
	int middle,right=size-1,left=0;
	while(right-left>1){
		middle=(right+left)/2;
		if(mas[middle]<n){left=middle;}
		else{right=middle;}
	}
	if(mas[middle]!=n){return -1;}
	else{return right;}
}

void sort_vib(int *mas,int size){
	int i,j,max,maxc=0,tmp;
	for(i=size-1;i>0;i--){
		max=mas[0];
		maxc=0;
		for(j=0;j<=i;j++){
			if(mas[j]>max){
				maxc=j;
				max=mas[j];
			}
		}
		tmp=mas[i];
		mas[i]=mas[maxc];
		mas[maxc]=tmp;
	}
	for(i=0;i<size;i++){
		printf("%5d",mas[i]);
	}
	return;
}