Одним из наиболее часто используемых действий в программировании является поиск данных. Существует несколько основных вариантов поиска, для которых созданы различные алгоритмы.
Линейный поиск-это называется поиском заданного значения произвольной функции в некотором сечении. Этот алгоритм считается простым алгоритмом, в отличие от других алгоритмов, таких как двоичный поиск, которые не имеют ограничений на функцию и просты в реализации.
Алгоритм линейного поиска
Поиск значения функции проверяется простым сравнением следующего значения (обычно в порядке возрастания аргумента слева направо). Задача может быть поставлена двояко: 1) Найти первый найденный аргумент 2) найти все аргументы.
Если в качестве аргумента массива в качестве функции используется индекс массива, то в результате линейного поиска необходимо найти такие индексы I из данного массива.
Массив: 45, 12 , 89, 12, -78, 12;
Позиции числа 12 2, 4, 6;
Линейный поиск.
В простом линейном поиске вы проверяете каждый элемент массива один за другим.int function LinearSearch (Array A, int L, int R, int Key);
begin
for X = L to R do
if A[X] = Key then
return X
return -1;
end;
В этом L и Р переменные-это диапазон, в котором ищется элемент.
O(n) шаги выполняются для каждого запроса. N-число элементов массива. Алгоритм линейного поиска эффективен только тогда, когда искомый интервал мал.
#include
using namespace std;
int a[10001];
void find(int a[], int left, int right, int k) {
bool found = 0;
for (int i = left; i <= right; i++) {
if (a[i]==k) {
found = 1;
cout<}
}
if (!found)
cout<<"-1";
cout<}
int main() {
int n;
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>a[i];//massiv elementlarini o'qitish
}
int k; // izlanayotgan son
cin>>k;
find(a, 1, n, k);
}
Допустим, нам дан массив:
a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
У нас есть условие для создания программы, которая может проверить, есть ли элемент в этом массиве.
Первый метод, который приходит на ум при решении этой задачи,-это сравнение каждого элемента массива в последовательности, и это метод:
Линейный поиск-называется линейным поиском, и код этого метода выглядит следующим образом:
func linearSearch(a []int, condidate int) int {
for i := 0; i < len(a); i++ {
if a[i] == condidate {
return i
}
}
return -1
}
Ко'риб турганингиздек, функционамиз 2 Та параметр кабул килади, биринчиси массивни О'зи, иккинчиси эса биз кидрайотган элемент. Агар уни топа олмасак, "-1 " кийматни кайтарамиз.
Энди бундан оптимальный Бо'лган усул - бинар(иккилик) кидирувни ко'риб чиксак.
Бу усулда хам функсияга 2 Та параметр, биринчиси массив О'зи кейин эса биз кидирайотган элементни параметр сифатида берилади. Кидирув эса куидагича:
Дастлаб биз массив боши ва оксирини О'зимиз учун О'згарувчиларда белгилаб оламиз, менинг кодимда бу слева ва справа О'згарувчиларидур:
left := 0 right := len(a)
тогда при выполнении следующего условия
left < right
выполняем следующие последовательные операции
находим элемент в центре индексов left и right lari (left + right) / 2
если наш найденный элемент равен элементу, который мы ищем, то мы возвращаем элемент Mid в качестве ответа если наш элемент a[mid] меньше элемента, который мы ищем, мы устанавливаем left = Mid, и тогда поиск будет продолжен в фрагменте a [mid:right]. если наш элемент a[mid] больше, чем элемент, который мы ищем, это означает, что мы определяем right = Mid так что поиск продолжается в фрагменте a [left:Mid].
В этом файле поиск продолжается до тех пор, пока условие left < Right не будет выполнено, если в процессе не будет найден элемент, который мы искали, то ответ -1 будет возвращен, ниже приведен программный код:
func binarySearch(a []int, condidate int) int {
left := 0
right := len(a)
for left < right {
mid := (left + right) / 2
if a[mid] == condidate {
return mid
}
if a[mid] < condidate {
left = mid
} else {
right = mid
}
}
return -1
}
Этот метод называется итеративным методом двоичного поиска, также этот алгоритм можно записать в рекурсивном методе, попробуйте написать рекурсивный метод самостоятельно, если вы не решите. Большинство программистов не могут написать это правильно с одной попытки, и это нормально, потому что там, где есть ошибка, будет возможность поработать над собой.
Теперь давайте рассмотрим некоторые аспекты этих методов поиска:
массив, назначаемый функции, обязательно должен быть в порядке возрастания для двоичного поиска, в то время как для линейного поиска не имеет значения, в каком порядке находится данный массив
в линейном поиске проверяется каждый из элементов по одному, в то время как в двоичном выполняется гораздо меньше операций сравнения, чем в линейном, исходя из алгоритма, время выполнения линейного поиска не более O(n) и двоичного поиска не более o(log N)
Кроме того, есть и другие способы поиска в массиве вы можете узнать об этом подробнее здесь.
Do'stlaringiz bilan baham: |
