Skip to content

Linear search

Quote

“When in doubt, use brute force.” — Ken Thompson

Case Time complexity Space complexity
Best \(\color{white} \fcolorbox{limegreen}{forestgreen} {Ω(1)}\)
Average \(\color{black} \fcolorbox{gold}{yellow} {Θ(n)}\)
Worst \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)

Linear search or sequential search, iterates through each element until item is found.

int linearSearch(int[] array, int target) {
    for (var i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i
        }
    }
    return -1
}

int linearSearch(int array[], int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;
}

fun linearSearch(array: IntArray, target: Int): Int {
    for (i in array.indices) {
        if (array[i] == target) {
            return i
        }
    }
    return -1
}

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}

def linear_search(array: list[int], target: int) -> int:
    for i in range(len(array)):
        if array[i] == target:
            return i
    return -1

function linearSearch(array: number[], target: number): number {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}

Use cases

  • The list to search is small