Как и в повседневной жизни, нам, как профессионалам в области программного обеспечения, необходимо искать информацию на нашем компьютере. Поиск информации должен осуществляться быстро, поскольку мы не можем позволить себе тратить много времени на ее поиск.
Следовательно, нам нужны некоторые эффективные методы поиска или алгоритмы, которые помогут искать заданную часть информации за короткое время и предоставят ее пользователю, чтобы он мог приступить к другим задачам.
Методы поиска
Есть два основных метода поиска, которые в основном используются для поиска информации, это:
- Линейный поиск
- Бинарный поиск
В этой статье мы подробно рассмотрим оба этих метода поиска.
Линейный поиск
Это самый простой метод поиска, и его легко реализовать. При линейном поиске искомый ключ линейно сравнивается с каждым элементом набора данных. Этот метод эффективно работает с линейными структурами данных.
Рассмотрим следующий массив:
Выше показан массив из семи элементов. Если мы хотим найти ключ = 23, то начиная с 0-го элемента значение ключа будет сравниваться с каждым элементом. Как только ключевой элемент совпадет с элементом в массиве, будет возвращено это конкретное местоположение. В этом случае будет возвращено значение 3, так как ключ-значение соответствует значению в этом местоположении.
Ниже мы реализовали линейный поиск с использованием языков C++ и Java.
Скетч на С++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <string> 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"<<endl; for(int i=0;i<10;i++){ cout<<myarray[i]<<" "; } cout<<endl; cout<<"Enter the key to be searched : "; cin>>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 "<<loc<<" in the array"; } else { cout<<"Could not find given key in the array"; } } |
Вывод данных:
| Входной массив: 21 43 23 54 75 13 5 8 25 10 Введите ключ для поиска: 3 Не удалось найти данный ключ в массиве Входной массив: 21 43 23 54 75 13 5 8 25 10 Введите ключ для поиска: 75 Ключ найден в позиции 5 в массиве |
Скетч на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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("\n"); 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"); } } |
Вывод данных:
| Входной массив6 21 43 23 54 75 13 5 8 25 10 Клавиша ввода6 23 ключ найден в локации: 3 |
Линейный поиск может выполняться для любой линейной структуры данных, имеющей отсортированные или несортированные элементы. Но это занимает больше времени, если элементов слишком много и если ключевой элемент находится ближе к концу, поскольку каждый элемент сравнивается со значением ключа.
Бинарный поиск
Бинарный поиск — это метод, который использует метод «разделяй и властвуй» для поиска ключа. Он работает с отсортированным линейным списком элементов. Отсортированный список является основным требованием для работы бинарного поиска.
В методе бинарного поиска список многократно делится пополам, и ключевой элемент ищется в обеих половинах списка, пока ключ не будет найден.
Например, возьмем следующий отсортированный массив из 10 элементов:
Допустим, ключ = 21 нужно искать в массиве.
Вычислим среднее расположение массива.
Середина = 0+9/2 = 4
Например, возьмем следующий отсортированный массив из 10 элементов:
Ключ = 21
Сначала мы сравним значение ключа с элементом [mid]. Мы видим, что значение элемента в середине = 21.
Таким образом, мы находим, что key = [mid], т.е. ключ = середина. Значит, ключ найден.
Сначала мы сравниваем значение ключа со значением mid. Итак (21 < 25), мы будем искать ключ непосредственно в верхней половине массива:
Теперь снова найдем середину верхней половины массива.
mid = 4+9/2 = 6
Значение в месте [mid] = 25
![ключ в локации [mid]](https://monitorbank.ru/wp-content/uploads/2022/08/Ключ-в-локации-mid.png)
Теперь мы сравниваем ключевой элемент со средним элементом. Итак (25 == 25), таким образом, мы нашли ключ в локации [mid].
Многократно деля массив и, сравнивая ключевой элемент со средним, решаем, в какой половине искать ключ.
Ниже приведены реализации скетча C++ и Java для бинарного поиска.
Реализация на С++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <string> 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) { return binarySearch(myarray,mid+1,end,key); } else { return binarySearch(myarray,beg,mid-1,key); } } return -1; } int main () { int myarray[10] = {5,8,10,13,21,23,25,43,54,75}; int key, location=-1; cout<<"The input array is"<<endl; for(int i=0;i<10;i++){ cout<<myarray[i]<<" "; } cout<<endl; cout<<"Enter the key that is to be searched:"; cin>>key; location = binarySearch(myarray, 0, 9, key); if(location != -1) { cout<<"Key found at location "<<location; } else { cout<<"Requested key not found"; } } |
Вывод данных:
| Входной массив: 5 8 10 13 21 23 25 43 54 75 Введите ключ для поиска: 21 Ключ найден в ячейке 5 . |
Реализация на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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<10;i++){ System.out.print(myarray[i]+" "); } System.out.println(); System.out.println("Enter the key to be searched"); Scanner sc = new Scanner(System.in); key = sc.nextInt(); location = binarySearch(myarray,0,9,key); if(location != -1) System.out.println("the location of the key is "+location); else System.out.println("Key not found"); } public static 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) { return binarySearch(myarray,mid+1,end,key); } else { return binarySearch(myarray,beg,mid-1,key); } } return -1; } } |
Вывод данных:
| Входной массив: 5 8 10 13 21 23 25 43 54 75 Введите ключ для поиска: 21 расположение ключа 5 |
Бинарный поиск более эффективен с точки зрения времени и корректности. Метод линейного поиска используется редко, так как он более громоздкий и медленный. Бинарный поиск намного быстрее по сравнению с линейным поиском.
Итог
Методы поиска помогают нам искать информацию, хранящуюся на компьютере, чтобы пользователь мог приступить к другим задачам обработки информации. Техника линейного поиска проста и легка, но широко не используется. Техника бинарного поиска намного быстрее и эффективнее, поэтому она и рекомендуется к использованию.
В нашей следующей статье мы подробно рассмотрим список различных методов сортировки в C++.
С Уважением, МониторБанк