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

[Аватар]

Ромаха, ты не понял. В задании найти бинарным поиском по нескольким условиям, первое ведущее. Например: найти на шахматной доске с4. Колонка ведущая, строка ведомая. Сортируем по ключу: колонка,строка. Обрати внимание - ключ сортировки составной. И поиск по составному ключу

[Poma][a]

Бинго! Дошло!
Нечто вида списка ребер, но с доп. полям, чтобы многократно крутить поиск.. Спасибо!!!

[Praud]

Можете объяснить как надо переделать код?
Я мало что понял из того что выше...

Допустим создаю я массив структур.

struct st
{
   int x;
};

st y[15];

Что мне с ним делать?
Как я уже понял искомых ключей должно быть несколько? и это созданный мною массив?
Я что-то совсем запутался

До всех короче дошло кроме меня

[Stilet]

Что мне с ним делать?

Использовать в условии, где сейчас у тебя

if (arr[j] > arr[j + 1])

Т.е.

if (y[j].x>y[i].x && y[j].ДругоеПоле>y[j].ДругоеПоле)

Получается сортировка по двум условиям - х и ДругоеПоле

[Praud]

Так мне же нужна не сортировка по нескольким условиям, а поиск!

Я забабахал вот такой вот код.

#include <iostream>
#include <locale.h>
#include <time.h>
using namespace std;

const int N = 5; 
const int COUNT = 3;

struct Table
{
	int x;
	int y;
};

int BinarySearch(Table[], int); //  Дихотомический поиск 
void BubbleSort(Table[]); // Пузырьковая сортировка

int main()
{
	setlocale(LC_ALL, "Rus"); // Русский язык в консоли

	srand(time(NULL)); 

	Table st[N];
	int keys[COUNT];

	for (int i = 0; i < N; i++)
	{
		st[i].x = 0 + rand() % 10; // Заполняем массив случайными числами
		st[i].y = 0 + rand() % 10; // Заполняем массив случайными числами
	}

	BubbleSort(st); // Сортируем массив по возрастанию

	cout << "Исходная таблица:" << endl;

	for (int i = 0; i < N; i++)
		cout << st[i].x << " ";  // Выводим массив в консоль
	
	cout << endl;

	for (int i = 0; i < N; i++)
		cout << st[i].y << " ";  // Выводим массив в консоль

	cout << endl;
	cout << "Введите ключи: " << endl;
	
	for (int i = 0; i < COUNT; i++)
	{
		cout << i + 1 << ") ";
		cin >> keys[i]; // Запрос ключа
	}
	
	for (int i = 0; i < COUNT; i++)
	{
		if (BinarySearch(st, keys[i]) != -1)
			cout << "Ключ " << keys[i] << " найден" << endl;
		else cout << "Ключ " << keys[i] << " не найден" << endl;
	}
	

	cout << endl;
	system("pause");
}

// Бинарный поиск
int BinarySearch(Table t[], int key)
{
	int l = t[0].x;  // нижняя граница
	int u = t[N -1].x;    // верхняя граница

	while (l <= u) 
	{
		int m = (l + u) / 2;  // средний элемент
		if (t[m].x == key) return m;
		if (t[m].x < key) l = m + 1;
		if (t[m].x > key) u = m - 1;
	}

	l = t[0].y;  // нижняя граница
	u = t[N - 1].y - 1;    // верхняя граница

	while (l <= u)
	{
		int m = (l + u) / 2;  // средний элемент
		if (t[m].y == key) return m;
		if (t[m].y < key) l = m + 1;
		if (t[m].y > key) u = m - 1;
	}

	return -1;
}

// Пузырьковая сортировка
void BubbleSort(Table t[])
{
	int temp;

	for (int i = 0; i < N - 1; i++)
		for (int j = 0; j < N - i - 1; j++)
			if (t[j].x > t[j + 1].x)
			{
				temp = t[j].x;
				t[j].x = t[j + 1].x;
				t[j + 1].x = temp;
			}

	for (int i = 0; i < N - 1; i++)
		for (int j = 0; j < N - i - 1; j++)
			if (t[j].y > t[j + 1].y)
			{
				temp = t[j].y;
				t[j].y = t[j + 1].y;
				t[j + 1].y = temp;
			}
}

При чем он у меня еще и через раз работает.
Комменты старые, можно не читать.
Что тут происходит щас расскажу...

Вводим массив ключей
"В качестве исходных данных рассматривать массив числовых ключей."

Сортируем массив структур одним махом.
Вначале поля x, затем y.

Далее ищем наши ключи в таблице и показываем какие есть, каких нет.

Это бред сумасшедшего, да ?

[Аватар]

Так мне же нужна не сортировка по нескольким условиям, а поиск!

А бинарный поиск не бывает без сортировки, хоть по однму условию, хоть по нескольким

[Stilet]

Это бред сумасшедшего, да ?

Ну я бы не сказал что бред, но пожалуй допилить его стоит.

[Praud]

Можете помочь определить где у меня ошибка в коде?
Сортирует нормально, а вот поиск через раз работает правильно.

[Stilet]

Я может сейчас неправильно напишу, но все же:

// Бинарный поиск
int BinarySearch(Table t[], int key)
{
	int l=0;  // нижняя граница
	int u = N;    // верхняя граница
        int i=N/2;
	while (l <= u) 
	{
		if (t[i].x == key) return m; else
		if (t[i].x < key) l = l+(u-l)/2;  else
		if (t[i].x > key) u =u-(u-l)/2;  
                i=(u-l)/2;
	}

	return -1;
}

[Praud]

Сообщение от Stilet

Я может сейчас неправильно напишу, но все же:

// Бинарный поиск
int BinarySearch(Table t[], int key)
{
	int l=0;  // нижняя граница
	int u = N;    // верхняя граница
        int i=N/2;
	while (l <= u) 
	{
		if (t[i].x == key) return m; else
		if (t[i].x < key) l = l+(u-l)/2;  else
		if (t[i].x > key) u =u-(u-l)/2;  
                i=(u-l)/2;
	}

	return -1;
}

return m?
и программа зависает, когда элемент не находится

P.S потестил, даже не всегда находит