Lineær søgning forklaret

Hvad er lineær søgning?

Antag, at du får en liste eller en række elementer. Du søger efter et bestemt emne. Hvordan gør du det?

Find tallet 13 på den givne liste.

Lineær søgning 1

Du ser bare på listen, og der er den!

Lineær søgning 2

Nu, hvordan fortæller du en computer at finde den?

En computer kan ikke se mere end værdien på et givet tidspunkt. Så det tager et element fra arrayet og kontrollerer, om det er det samme som det, du leder efter.

Lineær søgning 3

Det første element matchede ikke. Så gå videre til den næste.

Lineær søgning 4

Og så videre…

Dette gøres, indtil der er fundet et match, eller indtil alle emner er blevet kontrolleret.

Lineær søgning 5

I denne algoritme kan du stoppe, når varen findes, og så er der ingen grund til at se længere.

Så hvor lang tid ville det tage at udføre den lineære søgning? I bedste fald kan du være heldig, og den vare, du ser på, måske på den første position i arrayet!

Men i værste fald bliver du nødt til at se på hver eneste vare, før du finder varen på det sidste sted, eller inden du indser, at varen ikke er i arrayet.

Kompleksiteten ved lineær søgning er derfor O (n).

Hvis det element, der skal søges, levede på den første hukommelsesblok, ville kompleksiteten være: O (1).

Koden til en lineær søgefunktion i JavaScript er vist nedenfor. Denne funktion returnerer positionen for det element, vi leder efter i arrayet. Hvis elementet ikke er til stede i arrayet, returnerer funktionen null.

Eksempel i Javascript

function linearSearch(arr, item) { // Go through all the elements of arr to look for item. for (var i = 0; i < arr.length; i++) { if (arr[i] === item) { // Found it! return i; } } // Item not found in the array. return null; }

Eksempel i Ruby

def linear_search(target, array) counter = 0 while counter < array.length if array[counter] == target return counter else counter += 1 end end return nil end

Eksempel i C ++

int linear_search(int arr[],int n,int num) { for(int i=0;i
    

Example in Python

def linear_search(array, num): for i in range(len(array)): if (array[i]==num): return i return -1

Global Linear Search

What if you are searching the multiple occurrences of an element? For example you want to see how many 5’s are in an array.

Target = 5

Array = [ 1, 2, 3, 4, 5, 6, 5, 7, 8, 9, 5]

This array has 3 occurrences of 5s and we want to return the indexes (where they are in the array) of all of them.

This is called global linear search and you will need to adjust your code to return an array of the index points at which it finds your target element.

When you find an index element that matches your target, the index point (counter) will be added in the results array. If it doesn’t match, the code will continue to move on to the next element in the array by adding 1 to the counter.

def global_linear_search(target, array) counter = 0 results = [] while counter < array.length if array[counter] == target results << counter counter += 1 else counter += 1 end end if results.empty? return nil else return results end end

Why linear search is not efficient

There is no doubt that linear search is simple. But because it compares each element one by one, it is time consuming and therefore not very efficient. If we have to find a number from, say, 1,000,000 numbers and that number is at the last position, a linear search technique would become quite tedious.

So you should also learn about bubble sort, quick sort and other more efficient algorithms.

Other search algorithms:

  • How to implement quick sort
  • Binary search algorithm
  • Jump search algorithm
  • Search algorithms explained with examples
  • Implement a binary search algorithm in Java without recursion
  • More info on search algorithms