Searching

• Linear search

  ---

  Sequentially checks each element of the list until a match is found

  Use cases

• Binary search

  ---

  Compares the target value to the middle element of the array, eliminating half of the search range each iteration.

  Use cases

• Depth-first search

  ---

  Explores as far as possible along each branch before backtracking.

  Use cases

• Breadth-first search

  ---

  Explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

  Use cases

Performance overview

Search	Time complexity	Space complexity
Linear search	\(\color{white} \fcolorbox{limegreen}{forestgreen} {Ω(1)}\) → \(\color{black} \fcolorbox{gold}{yellow} {Θ(n)}\) → \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)	\(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Binary search	\(\color{white} \fcolorbox{limegreen}{forestgreen} {Ω(1)}\) → \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {Θ(log(n))}\) → \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\)	\(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Breadth-first search	\(\color{black} \fcolorbox{gold}{yellow} {Θ(│E│ + │V│)}\)	\(\color{black} \fcolorbox{gold}{yellow} {Θ(│V│)}\)
Depth-first search	\(\color{black} \fcolorbox{gold}{yellow} {Θ(│E│ + │V│)}\)	\(\color{black} \fcolorbox{gold}{yellow} {Θ(│V│)}\)