Линейный поиск

Поиск
В программировании это процесс нахождения заданной позиции значения в списке значений. В нашей повседневной жизни он играет очень важную роль, это может быть поиск чего-либо из коллекции данных, вам может понадобиться найти слово в словаре или найти своего друга в толпе.

Линейный/последовательный поиск

  • Это основной простой алгоритм поиска.
  • При последовательном поиске мы сравниваем целевое значение со всеми другими элементами, заданными в списке. напримерarr = {18, 12, 19, 77, 29, 50} (несортированный массив)target = 77

В приведенном выше примере целевое значение сравнивается со всеми элементами массива последовательным/линейным способом.

Временная сложность:

Лучший случай: O(1) -> константа
How many checks will the loop make in the best case i.e the element will be found at the 0th index that is only one comparison will be made for best case.
Вход в полноэкранный режим Выход из полноэкранного режима

Худший случай: O(n)

 Worst case, here it will go through every element and then it says element not found
Вход в полноэкранный режим Выход из полноэкранного режима

public class Main {

    public static void main(String[] args) {
        int[] nums = {23, 45, 1, 2, 8, 19, -3, 16, -11, 28};
        int target = 19;
        int ans = linearSearch(nums, target);
        System.out.println(ans);
    }
     // search in the array: return the index if item found
    // otherwise if item not found return -1
    static int linearSearch(int[] arr, int target) {
        if (arr.length == 0) {
            return -1;
        }

        // run a for loop
        for (int index = 0; index < arr.length; index++) {
            // check for element at every index if it is = target
            int element = arr[index];
            if (element == target) {
                return index;
            }
        }
        // this line will execute if none of the return statements above have executed
        // hence the target not found
        return -1;
    }

}
Войти в полноэкранный режим Выход из полноэкранного режима

Решил свой первый вопрос по leetcode с помощью линейного поиска, проверьте его Четное количество цифр
Для дальнейшего объяснения алгоритма линейного поиска, пожалуйста, ознакомьтесь с этим замечательным тотуриалом
Линейный поиск в Java от Кунала Кушваха

Не стесняйтесь общаться со мной на github и Linkedin, спасибо.

Оцените статью
Procodings.ru
Добавить комментарий