1 of 8

Search

  • Looking for values is super common
  • Linear search is easy to write and understand but inefficient
    • which matters if lots of data
    • you are doing lots of searching
  • Binary search is MUCH faster
    • but requires list to be sorted (which takes time)

1

2 of 8

Linear Search

2

3 of 8

Linear Search

  • Simple code
  • Inefficient (if you have n items, you might have to look through all of them
    • Takes O(n) time (Big O n)

3

4 of 8

Binary Search

If we were looking for 20

4

5 of 8

Looking for 37

5

6 of 8

Looking for 37

6

7 of 8

Looking for 37

7

8 of 8

Code:

  • Much longer to write
  • Requires the list is sorted
  • Much faster, each time, you eliminate half the remaining array
  • O(log2n)

​

8