Linear Search

DSA · Arrays and Searching

Theory

Linear search checks each element one by one from the start until it finds the target or reaches the end. It works on any list, sorted or not, and needs no extra memory. Its worst-case time is O(n) because the target may be last or missing; the best case is O(1) when the target is first.

Why we use it

It is the simplest search, requires no preparation, and is often the fastest choice for small or unsorted data.

When to use it

Use linear search for small lists, unsorted data, one-off searches, or when you need every match rather than one.

How it works

  1. Start: i = 0
  2. Is i < n? Yes: Compare arr[i] with target. No: Return -1 (not found).
  3. arr[i] == target? Yes: Return i (found). No: i = i + 1, repeat.

Syntax

for i from 0 to n-1:
    if arr[i] == target: return i
return -1

Time: O(n)   Space: O(1)

Example

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

cities = ["Pune", "Delhi", "Mumbai", "Jaipur"]
print("Mumbai found at index", linear_search(cities, "Mumbai"))
print("Chennai found at index", linear_search(cities, "Chennai"))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic