Linear Search & Kata Setup

The simplest search algorithm is the linear search.

array [                           ]
      |                           |
      0                           n

search(array, value)

We want a way to search through an array for a value.

array [ array[0] = value?         ]
      |    ^                      |
      0    |                      n
           |

We traverse the array, checking each value.

array [ array[0] array[1] = value?]
      |    ^      ^               |
      0    |      |               n
           |      |

(and so on)

Time Complexity

Recall the three principles of time complexity:

1. Growth is with respect to the input.
2. Constants are dropped.
3. Consider the worst case.

Assuming the worst case, we would have to go from 0 to n, checking each value.

So, the time complexity is .

Implementation

fn linear_search<T: PartialEq>(arr: &[T], value: T) -> Option<usize> {
    for (i, v) in arr.iter().enumerate() {
        if v == &value {
            return Some(i);
        }
    }
    None
}

function linearSearch<T>(arr: T[], value: T): number | null {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === value) {
            return i;
        }
    }
    return null;
}