Автор оригинала: Pankaj Kumar.
Последовательный поиск – это прямой способ поиска элемента в коллекции. Этот тип поиска использует цикл, чтобы просмотреть каждый элемент по одному и посмотреть, совпадает ли он с элементом, который мы ищем. Механизм поиска движется в определенной последовательности, отсюда и название последовательного поиска.
В случае, если данные отсортированы, мы можем сократить количество запросов. Мы можем остановить поиск, когда превысим целевой элемент. Это возможно только в том случае, если целевой элемент отсутствует.
Простой Последовательный Поиск
В случае несортированных данных метод поиска проходит по всем элементам. В каждой позиции он сравнивает элемент в этой позиции с тем, который мы ищем. Если мы находим совпадение, мы возвращаем значение true, в противном случае мы продолжаем наш поиск. Если мы дойдем до конца и совпадение не будет найдено, мы вернем false.
package com.journaldev.java;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] a = {3,2,4,5,3,2,7,6,4};
boolean ans = contains(a,7);
if(ans) {
System.out.println("Number found");
}
else{
System.out.println("Number not found");
}
}
public static boolean contains(int[] a, int b){
for (int i : a) {
if (i==b){
return true;
}
}
return false;
}
}
Последовательный поиск в Отсортированном массиве
Последовательный поиск по отсортированным данным не всегда снижает сложность или количество поисковых запросов, которые нам необходимо выполнить. Однако в случае, если элемент отсутствует, мы можем остановить наш поиск в тот момент, когда наш поиск превысит целевой элемент.
package com.journaldev.java;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] a = {1,2,3,4,6,7,9};
boolean ans = contains(a,5);
if(ans) {
System.out.println("Number found");
}
else{
System.out.println("Number not found");
}
}
public static boolean contains(int[] a, int b){
for (int i : a) {
System.out.println("Comparing with :" +i);
if (i==b){
return true;
}
else if(i>b){
return false;
}
}
return false;
}
}
В этом коде мы печатаем номер, с которым сравнивается наш механизм поиска. Мы видим, что поиск останавливается на 6, так как 6 уже больше 5, и если мы выйдем за пределы 6, мы столкнемся только с числами, превышающими 6.
Здесь важно отметить, что наихудшая сложность по-прежнему остается O(n). Так как в худшем случае элемент, который мы ищем, может быть последним элементом, и нам нужно будет просмотреть весь массив.
Вывод
Последовательный поиск-это самый простой механизм поиска для поиска в массивах. Помимо массивов, также часто используется последовательный поиск для поиска элементов в Связанном списке. Наихудшая сложность последовательного поиска-O(n), где n-общее количество элементов.