lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

Linear Search.md (525B)

      1 +++
      2 title = 'Linear Search'
      3 +++
      4 # Linear Search (sequential search)
      5 - simplest search algorithm for finding particular element in a list
      6 - efficient for small lists
      7 - belongs to the “Brute force” strategy
      8 
      9 How it works:
     10 
     11 each element in list is checked one by one based on a condition until desired element is found
     12 
     13 element found => location returned, algorithm stops
     14 
     15 Performance:
     16 
     17 - Best case: 1 comparison
     18 - Worst case: n comparisons
     19 - Average: (n+1)/2 comparisons
     20 
     21 Time complexity:
     22 
     23 - Worst case n comparisons: O(n)