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

 

 

 

 

 

Текст библиотеки

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ClassLibraryBinPoisk
{
/// <summary>
/// Класс, описывающий переменные и процедуры бинарного поиска
/// </summary>
public class Bin_Search
{
int size;//Переменная размера массива
int[] sourse_array;//Исходный массив
int[] array_sorted;//Отсортированный массив
int pattern;//Переменная образца
Random rnd = new Random();//Переменная рандомных чисел

/// <summary>
/// Создает новый (исходный) массив из случайных чисел
/// </summary>
/// <param name=»size»>размер массива</param>
/// <param name=»sourse_array»>создающийся массив</param>
public void Create_Array(int size, out int[]sourse_array)
{
sourse_array = new int[size];
for (int i = 0; i < size; i++)
{ sourse_array[i] = rnd.Next(100); }

}
/// <summary>
/// Сортирует массив методом «пузырёк» по возрастанию
/// </summary>
/// <param name=»size»>размер массива</param>
/// <param name=»sourse_array»>исходный массив</param>
/// <param name=»array_sorted»>отсортированный массив</param>
public void Sort_Array(int size, int[]sourse_array, out int[]array_sorted)
{
for (int i = 0; i < size — 1; i++)
for (int j = size — 1; j > i; j—)
{
///Обмен значений
if (sourse_array[j] < sourse_array[j - 1])
{
int temp = sourse_array[j];
sourse_array[j] = sourse_array[j - 1];
sourse_array[j - 1] = temp;
}

}

array_sorted = sourse_array;
}
/// <summary>
/// Выполняет бинарный поиск образца в массиве
/// </summary>
/// <param name=»size»>размер массива</param>
/// <param name=»array_sorted»>отсортированный массив</param>
/// <param name=»pattern»>образец</param>
/// <param name=»message»>сообщение о результате</param>
public void Binar_Search(int size, int[]array_sorted, int pattern, out string message)
{
int first_border = 0;
int last_border = size;
int middle;
///Если массив пустой, выдается соответствующее сообщение
if (size == 0)
{
message = «Пустой массив»;
}
///Если образец меньше минимального или больше максимального члена массива, то
///поиск не выполняется и выдается соответствующее сообщение
else
if (pattern < array_sorted[0] || pattern > array_sorted[size - 1])
{
message = «Образец находится за рамками массива»;
}
else
{
///Выполняется поиск: границы поиска сдвигаются, пока не будет получен результат
while (first_border < last_border)
{
///Расчет середины массива
middle = first_border + (last_border — first_border) / 2;
///Установка верхней и нижней границы поиска
if (pattern <= array_sorted[middle])
{
last_border = middle;
}
else
{
first_border = middle + 1;
}
}
///Анализ результатов: если образец найден рассчитывается количество вхождений и номер
///первого вхождения
if (array_sorted[last_border] == pattern)
{
int N = last_border + 1;
int i = last_border;
while (array_sorted[i] == pattern & i < size — 1)
{
i++;
}
int I = i — last_border;
if (i == size — 1)
{ I = I + 1; }
message = «Образец обнаружен. Номер первого вхождения в отсортированном массиве:»
+ N + «Количество вхождений:» + I;

}
///Если образец не найден, выдается соответствующее сообщение
else
{
message = «Образец не обнаружен»;
}
}

}
}
}

Текст приложения WindowsForm

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using ClassLibraryBinPoisk;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
/// <summary>
/// Программа создает массив из случайных чисел, сортирует его и выполняет бинарный поиск
/// в отсортированном массиве
/// </summary>
int size;//Переменная размера
int[] sourse_array;//Исходный массив
int[] array_sorted;//Отсортированный массив
string message;//Сообщение о результате
Random rnd = new Random();//Переменная случайного числа
Bin_Search my_searh = new Bin_Search();//Создание члена класса Bin_Search
/// <summary>
/// Кнопка «показать массив»
/// </summary>
/// <param name=»sender»></param>
/// <param name=»e»></param>
private void buttonshow_Click(object sender, EventArgs e)
{
size = Convert.ToInt32(textBoxrazm.Text);
my_searh.Create_Array(size, out sourse_array);
listBoxsourse.Items.Clear();
for (int i = 0; i < size; i++)
{ listBoxsourse.Items.Add(sourse_array[i]); }

}
/// <summary>
/// Кнопка «отсортировать массив»
/// </summary>
/// <param name=»sender»></param>
/// <param name=»e»></param>
private void buttonsort_Click(object sender, EventArgs e)
{
size = Convert.ToInt32(textBoxrazm.Text);
my_searh.Sort_Array(size, sourse_array, out array_sorted);
listBoxsorted.Items.Clear();
for (int i = 0; i < size; i++)
{ listBoxsorted.Items.Add(array_sorted[i]); }

}
/// <summary>
/// Кнопка «сравнить с образцом»
/// </summary>
/// <param name=»sender»></param>
/// <param name=»e»></param>
private void buttoneval_Click(object sender, EventArgs e)
{
size = Convert.ToInt32(textBoxrazm.Text);
int pattern = Convert.ToInt32(textBoxobr.Text);
my_searh.Binar_Search(size, array_sorted, pattern, out message);
textBoxres.Text = message;

}
}
}

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