Меню

Въведение в търсенето на алгоритми в C ++

introduction searching algorithms c

Опитайте Нашия Инструмент За Премахване На Проблемите

Преглед на алгоритмите за търсене в C ++.

Продължаваме да търсим нещо или другото в нашето ежедневие. Подобно на нашето ежедневие, като софтуерен професионалист, ние трябва да търсим информация на нашия компютър. Извличането на информация трябва да става бързо, тъй като не можем да си позволим да губим голяма част от времето си в търсене на информация.

Следователно се нуждаем от някои ефективни техники за търсене или алгоритми, които могат да търсят дадена информация за кратко време и да я предоставят на потребителя, така че потребителят да може да продължи с другите задачи.

=> Посетете тук за пълния списък с уроци за C ++.

ТЪРСЕНЕ НА АЛГОРИТМИ В C ++

Какво ще научите:

Техники за търсене

Имаме две основни техники за търсене, които се използват най-вече за търсене на информация.

Те включват:

  • Линейно търсене
  • Двоично търсене

В този урок ще разгледаме подробно и двете техники за търсене.

Линейно търсене

Това е най-основната техника за търсене и е по-лесна за изпълнение. При линейно търсене ключът за търсене се сравнява линейно с всеки елемент от събирането на данни. Тази техника работи ефективно върху линейни структури от данни.

Нека разгледаме следния масив.

Масив за линейно търсене

По-горе е масивът от седем елемента. Ако искаме да търсим ключ = 23, тогава започвайки от 0тиелемент, ключовата стойност ще бъде сравнена с всеки елемент. След като ключовият елемент съвпадне с елемента в масива, тогава това конкретно местоположение ще бъде върнато. В този случай местоположението 4 ще бъде върнато, тъй като ключ-стойност съответства на стойността в това местоположение.

Приложихме линейно търсене, използвайки C ++ и Java език по-долу.

Внедряване на C ++

#include #include using namespace std; int main() { int myarray(10) = {21,43,23,54,75,13,5,8,25,10}; int key,loc; cout<<'The input array is'<key; for (int i = 0; i<10; i++) { if(myarray(i) == key) { loc = i+1; break; } else loc = 0; } if(loc != 0) { cout<<'Key found at position '<

Изход:

приложение за шпиониране на друг телефон

Входният масив е
21 43 23 54 75 13 5 8 25 10
Въведете ключа за търсене: 3
Не можах да намеря даден ключ в масива

Входният масив е
21 43 23 54 75 13 5 8 25 10
Въведете ключа за търсене: 75
Ключът е намерен на позиция 5 в масива

Внедряване на Java

import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main(String() args) { int() myarray = {21,43,23,54,75,13,5,8,25,10}; int key,location=0; Scanner sc = new Scanner(System.in); System.out.println('The input array is'); for(int i=0;i<10;i++){ System.out.print(myarray(i)+' '); } System.out.println(' '); System.out.println('Enter key'); key = sc.nextInt(); for(int i = 0; i<10; i++) { if(myarray(i)==key) { location = i+1; break; } else location = 0; } if(location != 0) { System.out.println('key found at location ' + location); } else System.out.println('Key not found'); } }

Изход:

Входният масив е

21 43 23 54 75 13 5 8 25 10

Клавиш Enter

2. 3

ключ, намерен на място 3

Линейно търсене може да се извърши на всяка линейна структура от данни със сортирани или несортирани елементи. Но отнема повече време, ако има твърде много елементи и ако ключовият елемент е към края, тъй като всеки елемент се сравнява с ключовата стойност.

Двоично търсене

Бинарното търсене е техника, която използва техниката „разделяй и владей“ за търсене на ключ. Работи върху сортиран линеен списък с елементи. Сортираният списък е основното изискване за работа на двоично търсене.

При двоичния метод за търсене списъкът се разделя многократно наполовина и ключовият елемент се търси в двете половини на списъка, докато ключът бъде намерен.

Например,нека вземем следния сортиран масив от 10 елемента.

Двоично търсене

Да кажем, че ключът = 21 трябва да се търси в масива.

Нека изчислим средното местоположение на масива.

Mid = 0 + 9/2 = 4

Например,нека вземем следния сортиран масив от 10 елемента.

как да отворите .json файлове

изчислете средното местоположение

Ключ = 21

Първо ще сравним ключовата стойност с елемента (mid). Установяваме, че стойността на елемента в средата = 21.

сравнете стойността на ключа с елемента (mid)

Така намираме този ключ = (mid). Следователно ключът е намерен.

ключ = 25

ключ = (средата)

Първо сравняваме ключовата стойност със средата. Така че (21<25), we will directly search for the key in the upper half of the array.

сравнете ключовата стойност със средата

Сега отново ще намерим средата за горната половина на масива.

Средна = 4 + 9/2 = 6

Стойността в местоположението (mid) = 25

Стойността в местоположението (mid) = 25

Сега сравняваме ключовия елемент със средния елемент. И така (25 == 25), така че намерихме ключа на място (средата).

Многократно разделяме масива и като сравняваме ключовия елемент със средата, решаваме в коя половина да търсим ключа.

По-долу са дадени внедряването на C ++ и Java за двоично търсене.

Внедряване на C ++

#include #include using namespace std; int binarySearch(int myarray(), int beg, int end, int key) { int mid; if(end >= beg) { mid = (beg + end)/2; if(myarray(mid) == key) { return mid+1; } else if(myarray(mid) key; location = binarySearch(myarray, 0, 9, key); if(location != -1) { cout<<'Key found at location '<

Изход:

Входният масив е
5 8 10 13 21 23 25 43 54 75
Въведете ключа, който ще се търси: 21
Ключът е намерен на място 5

Двоично търсене c ++

Внедряване на Java

import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String() args) { int() myarray = {5,8,10,13,21,23,25,43,54,75}; int key, location = -1; System.out.println('The input array is'); for(int i=0;i= beg) { mid = (beg + end)/2; if(myarray(mid) == key) { return mid+1; } else if(myarray(mid)

Изход:

Входният масив е

5 8 10 13 21 23 25 43 54 75

Въведете ключа за търсене

двадесет и едно

местоположението на ключа е 5

c ++ вградени функции

Бинарното търсене е по-ефективно по отношение на времето и коректността. Техниката на линейно търсене се използва рядко, тъй като е по-тромава и по-бавна. Двоичното търсене е много по-бързо в сравнение с линейното търсене.

Заключение

Техниките за търсене ни помагат да търсим информация, съхранявана на компютър, така че потребителят да може да продължи с останалите задачи по обработка на информация. Техниката на линейно търсене е проста и лесна, но не се използва широко.

Техниката на двоично търсене е много по-бърза и ефективна, поради което се използва широко.

В нашия предстоящ урок ще разгледаме подробно различните техники за сортиране.

=> Вижте Перфектното ръководство за обучение на C ++ тук.

Препоръчително четене

^