Інтерполюються пошук в С ++ алгоритм пошуку

Вгадайте, яке найулюбленіше заняття багатьох викладачів? підказую: Відмовити в своїх класних кімнатах страшно академічні слівця, щоб у студентів волосся стало дибки від мегаулетності його сенсея. Одне з таких підступних словечок, валить молодих людей в шок – інтерполяція. Пропоную оглянути це чудо математичної думки з самого найпростішого ракурсу і використовуючи мінімум коду, щоб не муляли очі тоннами операторів, заплутуючи себе в теорії.

Итак, для начала – що ж це за слово таке “інтерполяція”? інтерполяція – це (якщо говорити мовою студента) визначення області пошуку, шляхом обчислення подібності відстаней між шуканим значенням і всією областю. Пам'ятайте по геометрії подобу трикутників? вони, у яких однакові за значенням кути, але пропорції різні. Тут практично той же принцип. Обчислюється довжина області пошуку, і довжина від початку області до якогось числа (скажімо до центрального елемента в масиві). Обчислення це проводиться як з номерами елемента, так і з їх значеннями, після чого отримана довжина області множиться на довжину між значеннями, і результат доданий до значення з початку області дає шукане.

Складно відразу зрозуміти на словах, тому спробую показати картинкою:

Формула досить проста – обчислюється довжина між номерами першого елемента і шуканого (задається точніше). Така ж довжина вважається між першим і останнім номерами. Довжини між собою діляться, як раз і отримуючи обчислення подібності. Те ж саме відбувається зі значеннями елементів – так само обчислюється відстань між граничними значеннями в масиві. Спеціально виділяю кольором поняття і пов'язані з ними частини формули.

Отримана довжина номерів елементів масиву множиться на довжину значень в цих (межують) елементах і додається значення в першій клітинці масиву.

Получается: 1 + (20-1)/(100-1) * (200-5) = 38 з копійками.

Результат і є те саме шукане. Тобто,. при таких значеннях як на картинці в осередку №20 буде стояти 38. Ось і весь сенс інтерполяції – складання подібності між номерами елементів і між значеннями елементів.

На С ++ це виглядає так:

#include <iostream>
using namespace std;

int main()
{
	//Массив значений в котором пойдет поиск
	int MyArray[] { 1, 2, 4, 6, 7, 89, 123, 231, 1000, 1235 };

	int x = 0; //Текущая позиция массива, с которым сравнивается искомое
	int a = 0; //Левая граница области, где ведется поиск
	int b = 9; //Правая граница области, где ведется поиск

	int WhatFind = 123; //Значение, которое нужно найти
	bool found; //Переменка-флаг, принимающая True если искомое найдено

	/************ Начало интерполяции *******************************/

	//Цикл поиска по массиву, пока искомое не найдено 
	//или пределы поиска еще существуют
	for (found = false; (MyArray[a] < WhatFind) && (MyArray[b] > WhatFind) && !found; )
	{
		//Вычисление интерполяцией следующего элемента, который будет сравниваться с искомым
		x = a + ((WhatFind - MyArray[a]) * (b - a)) / (MyArray[b] - MyArray[a]);
		//Получение новых границ области, если искомое не найдено
		if (MyArray[x] < WhatFind)   
			a = x + 1;
		else if (MyArray[x] > WhatFind)   
			b = x - 1;
		else
			found = true;
	}

	/************** Конец интерполяции ***************************/

	//Если искомое найдено на границах области поиска, показать на какой границе оно
	if (MyArray[a] == WhatFind) 
		cout << WhatFind << " founded in element " << a << endl;
	else if (MyArray[b] == WhatFind) 
		cout << WhatFind << " founded in element " << b << endl;
	else
		cout << "Sorry. Not found" << endl; 
	
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

//Массив значений в котором пойдет поиск

int MyArray[] { 1, 2, 4, 6, 7, 89, 123, 231, 1000, 1235 };

int x = 0; //Текущая позиция массива, с которым сравнивается искомое

int a = 0; //Левая граница области, где ведется поиск

int b = 9; //Правая граница области, где ведется поиск

int WhatFind = 123; //Значение, которое нужно найти

bool found; //Переменка-флаг, принимающая True если искомое найдено

/************ Начало интерполяции *******************************/

//Цикл поиска по массиву, пока искомое не найдено

//или пределы поиска еще существуют

for (found = false; (MyArray[a] < WhatFind) && (MyArray[b] > WhatFind) && !found; )

{

//Вычисление интерполяцией следующего элемента, который будет сравниваться с искомым

x = a + ((WhatFind - MyArray[a]) * (b - a)) / (MyArray[b] - MyArray[a]);

//Получение новых границ области, если искомое не найдено

if (MyArray[x] < WhatFind)

a = x + 1;

else if (MyArray[x] > WhatFind)

b = x - 1;

else

found = true;

}

/************** Конец интерполяции ***************************/

//Если искомое найдено на границах области поиска, показать на какой границе оно

if (MyArray[a] == WhatFind)

cout << WhatFind << " founded in element " << a << endl;

else if (MyArray[b] == WhatFind)

cout << WhatFind << " founded in element " << b << endl;

else

cout << "Sorry. Not found" << endl;

return 0;

}

Таким чином сам цикл просто обчислює за формулою область масиву, де може перебувати шукане використовуючи цей самий принцип інтерполяції в С ++, підбираючи подібності так би мовити. Якщо обчислене не дорівнює шуканого, значить потрібно зрушити кордону області, де проходить обчислення.

Якщо обчислене більше – зсувається права межа області пошуку, якщо менше – ліва. так відрізаючи (як в бінарному пошуку) шматок масиву за шматком поступово досягається потрібна комірка масиву, ну або кордону області пошуку звужуються до таких величин, в межах якого вже шукати нічого, коли дистанція між кордонами дорівнює 1 (т.е. між точкою А і В немає більше елементів для обчислення) рішення говорить про те, що значення в масиві, не знайдено.

Як бачите сам цикл не настільки вже й складний і жахливий. Вся сіль то прихована в його форумі. А решта – просто перевірки: знайшли або далі шукати. Ось така от вона… інтерполяція в C ++

Інтерполяційний пошук в чомусь нагадує двоичный. Тільки в ньому область пошуку не ділиться на дві рівні частини. Замість цього проводиться оцінка нової області пошуку по відстані між поточним значенням елемента і ключем пошуку. Швидкість роботи інтерполюючого пошуку перевершує швидкість довічного. Ще одна вагома відмінність інтерполюючого пошуку від довічного – можливість шукати текстову інформацію, а не тільки числові значення.

6 думки про "інтерполюються пошук”

Ілля говорить:
04.07.2016 at 11:23
Думаю це одна з тих тем, яка на практиці простіше ніж на словах)
відповісти
Михайло говорить:
09.04.2017 at 20:47
У коді помилка : для масиву { 52,26,64 ,53, 46, 53, 39, 54, 41, 40, 38 ,53, 38, 45, 32, 29 ,40, 41 } неправильно знаходить індекс числа 45. виправляється легко.
відповісти
1. Михайло говорить:
  09.04.2017 at 20:48
  природно, якщо масив спочатку впорядкувати за зростанням.
  відповісти
Іван говорить:
11.04.2019 at 05:28
Двійковий пошук прекрасно шукає текстову інформацію.
відповісти
Джуліан говорить:
01.10.2021 at 11:33
Трохи поліпшив ваш код, так як алгоритм не працював з масивом [0…9] например, тоесть коли a = 0, b = колічество_елементов – 1.
Потрібно просто додати код
else if (MyArray[x] == WhatFind)
cout << WhatFind << " знайдено в елементі " << x << endl;
в потрібне місце.
змінено:
#include
#include
using namespace std;
#визначити N 10
int main()
{
int MyArray[N] = {0,1,2,3,4,5,6,7,8,10};
/*for (int i = 0; i < N; i )
{
MyArray[i] = i;
}*/
INT х = 0;
int a = 0;
int b = N-1;
int WhatFind = 10;
bool знайдено;
for (знайдено = брехня; (MyArray[a] WhatFind) && !знайдений; )
{
x = a + ((WhatFind – MyArray[a]) * (b – a)) / (MyArray[b] – MyArray[a]);
if (MyArray[x] WhatFind)
б = х – 1;
else
знайдено = правда;
}
if (MyArray[a] == WhatFind)
cout << WhatFind << " знайдено в елементі " << a << endl;
else if (MyArray[b] == WhatFind)
cout << WhatFind << " знайдено в елементі " << b << endl;
else if (MyArray[x] == WhatFind)
cout << WhatFind << " знайдено в елементі " << x << endl;
else
cout << "Sorry. Не знайдено" << endl;
return 0;
}
відповісти
AleOP говорить:
31.08.2023 at 17:06
В загальному, пошук працює тільки у відсортованому масиві, як у випадку і з бінарним пошуком. Було б добре, якби подібна інформація вказувалася, але всеодно – дякую за інфу.
відповісти