Меню

Вступ до пошуку алгоритмів у C ++

introduction searching algorithms 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

Введіть ключ

2. 3

ключ, знайдений за адресою 3

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

Двійковий пошук

Бінарний пошук - це техніка, яка використовує техніку «розділи і владай» для пошуку ключа. Він працює над відсортованим лінійним списком елементів. Відсортований список - основна вимога для роботи двійкового пошуку.

У двійковому методі пошуку список неодноразово ділиться навпіл і ключовий елемент шукається в обох половинах списку, поки не буде знайдений ключ.

Наприклад,візьмемо наступний відсортований масив із 10 елементів.

Двійковий пошук

Скажімо, ключ = 21 слід шукати в масиві.

Обчислимо середнє розташування масиву.

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

Наприклад,візьмемо наступний відсортований масив із 10 елементів.

обчислити середнє розташування

Ключ = 21

Спочатку ми порівняємо значення ключа з елементом (mid). Ми виявили, що значення елемента в середині = 21.

порівняйте значення ключа з елементом (mid)

Таким чином, ми знаходимо, що ключ = (середина). Звідси ключ знайдений.

ключ = 25

як витягти торрентований файл - -

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

Спочатку ми порівнюємо ключове значення із середнім. Отже (21<25), we will directly search for the key in the upper half of the array.

порівняйте ключове значення із середнім

Тепер знову ми знайдемо середину для верхньої половини масиву.

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

Значення в місці (середина) = 25

Значення в місці (середина) = 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)

Вихід:

перетворити символ у рядок c ++

Вхідний масив:

5 8 10 13 21 23 25 43 54 75

Введіть ключ для пошуку

двадцять один

розташування ключа - 5

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

Висновок

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

Техніка двійкового пошуку набагато швидша та ефективніша, тому широко використовується.

У нашому майбутньому підручнику ми детально вивчимо різні методи сортування.

=> Ознайомтесь з Ідеальним навчальним посібником для C ++ тут.

Рекомендована література

^