Qidirish algoritmlari va ularning taxlili C#
![massivdan ikkilik qidiruv usuli yordamida key kalitga mos elementni izlash
dasturini ko’rib chiqamiz.
Dastur kodi: #include using namespace std; int main(){ int n;cout<<"n=";cin>>n;
int k[n]; for(int i=0;i>k[i]; int key, search; cout<<"qidirilayotgan elementni
kiriting=";cin>>key; int low = 0; int hi = n-1; int j=0; while (low <= hi){ int mid =
(low + hi) / 2;j++; if (key == k[mid]){ search = mid; cout<<"qidirilayotgan
element "<<search+1<<" o’rinda turibdi va u "<<j<<" ta solishtirishda toplidi\n";
system("pause"); exit(0); } if (key < k[mid]) hi = mid - 1; else low = mid + 1; }
search=-1; cout<<j<<" ta solishtirish amalga oshirildi va qidirilayotgan element
topilmadi\n"; system("pause"); } Dastur natijasi n=6 1 2 3 4 5 6 qidirilayotgan
elementni kiriting=6 qidirilayotgan element 6 o'rinda turibdi va u 3 ta solishtirishda
toplidi
Qidiruv jadvalini qayta tartibga keltirish Umuman olganda, jadvalda har bir
elementni qidirish ehtimolligini qandaydir bir qiymat bilan izohlash mumkin.
Faraz qilaylik jadvalda qidirilayotgan element mavjud. U holda qidiruv amalga
oshirilayotgan jadvalni diskret holatga ega tizim sifatida qarash mumkin hamda
unda qidirilayotgan elementni topish ehtimolligi – bu tizim i-chi holati ehtimolligi
p(i) deb olish mumkin. Jadvalni diskret tizim sifatida qaraganimizda, undagi
taqqoslashlar soni diskret tasodifiy miqdorlar qiymatlarini matematik kutilmasini
ifodalaydi.
Ma’lumotlar jadvalda quyidagi ko’rinishda tartiblangan bo’lishi lozim: Bu
shart taqqoslashlar sonini kamaytirib, samaradorlikni oshiradi. Sababi, ketma-ket
qidiruv birinchi elementdan boshlanganligi uchun eng ko’p murojaat qilinadigan
elementni birinchiga qo’yish lozim.
Qidiruv jadvalini qayta tartibga keltirishning eng ko’p ishlatiladigan ikkita
usuli mavjud. Ularni bir bog’lamli ro’yhatlar misolida ko’rib chiqamiz. 1. Topilgan
elementni ro’yhat boshiga qo’yish orqali qayta tartibga keltirish. 2. Transpozitsiya
usuli. 5.5. Topilgan elementni ro’yhat boshiga qo’yish orqali qayta tartibga
keltirish 2.2-rasm. Ro’yxatni qayta tartibga keltirish
17](https://docx.uz/documents/eebe9892-3087-40b8-887c-0d08fcc48573/page_17.png?v=1)
![Ilova
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BinarySearch
{
class BinaryArray
{
private int[] data;
private static Random generator = new Random();
public BinaryArray(int size)
{
data = new int[size];
for (int i = 0; i < size; i++)
{
data[i] = generator.Next(10, 100);
}
Array.Sort(data);
}
public int BinarySearch(int searchElement)
{
int low = 0;
int high = data.Length - 1;
int middle = (low + high + 1) / 2;
22](https://docx.uz/documents/eebe9892-3087-40b8-887c-0d08fcc48573/page_22.png?v=1)
![int location = -1;
do // Search for element
{
Console.Write(RemainingElements(low, high));
for (int i = 0; i < middle; i++)
Console.Write(" ");
Console.WriteLine(" * ");
if (searchElement == data[middle])
location = middle;
else if (searchElement < data[middle])
high = middle - 1;
else
low = middle + 1;
middle = (low + high + 1) / 2; // recalculate the middle
} while ((low <= high) && (location == -1));
return location; // return location of search key
}
public string RemainingElements(int low, int high)
{
string temporary = string.Empty;
for (int i = 0; i < low; i++)
temporary += " ";
// output elements left in array
for (int i = low; i <= high; i++)
temporary += data[i] + " ";
temporary += "\n";
return temporary;
}
23](https://docx.uz/documents/eebe9892-3087-40b8-887c-0d08fcc48573/page_23.png?v=1)
Qidirish algoritmlari va ularning taxlili C#