Searching in Arrays

What Is Array Searching?

Array searching is the process of finding a particular element or determining whether an element exists in an array. Searching is one of the most common operations performed on arrays because applications frequently need to locate values before reading, updating, or removing them.

The appropriate searching technique depends on factors such as whether the array is sorted, how frequently searches are performed, and whether the application needs the first matching element, every matching element, or simply confirmation that a value exists.

A Simple Array Search

Consider an array containing several numbers:

const numbers = [15, 28, 42, 63, 91];

If we want to find 42, a search operation needs to determine where that value occurs.

Target: 42

[15, 28, 42, 63, 91]
          ^
       Found

The result can be represented by its index:

Index of 42 = 2

Searching by Index vs Searching by Value

Accessing an array element by its known index is different from searching for a value. Arrays provide direct indexed access, so retrieving an element when its index is already known is typically O(1).

const numbers = [15, 28, 42, 63, 91];

console.log(numbers[2]);
// 42

However, if the index is unknown and we only know the value we are looking for, the array must be searched.

const index = numbers.indexOf(42);

console.log(index);
// 2

Common Array Searching Techniques

Two fundamental searching techniques are commonly introduced when studying arrays:

• Linear search checks elements sequentially.
• Binary search repeatedly divides a sorted search range in half.

These algorithms have different requirements and performance characteristics.

Linear Search

Linear search examines array elements one at a time from the beginning until the target value is found or the end of the array is reached.

Array:
[18, 7, 34, 52, 11]

Target:
52

Check:
18 → no
7  → no
34 → no
52 → found

Linear search does not require the array to be sorted, which makes it useful for small or unsorted collections.

Linear Search Example

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

  return -1;
}

const numbers = [18, 7, 34, 52, 11];

console.log(linearSearch(numbers, 52));
// 3

The function returns the index of the first matching element. If the target is not found, it returns -1.

Binary Search

Binary search is a more efficient searching technique for sorted arrays. Instead of checking every element, it compares the target with the middle element and eliminates half of the remaining search space after each comparison.

Sorted array:

[10, 20, 30, 40, 50, 60, 70]

Target: 60

Check middle:
40

60 is greater than 40,
so search the right half:

[50, 60, 70]

Check middle:
60 → found

Binary search can achieve O(log n) search time, but the data must satisfy the ordering requirement used by the algorithm.

Linear Search vs Binary Search

The main difference is how the algorithms reduce the search space. Linear search moves through elements sequentially, while binary search eliminates approximately half of the remaining range at every step.

Searching in Sorted and Unsorted Arrays

Whether an array is sorted has a major effect on the available searching strategies.

Unsorted Array

For an unsorted array, linear search is a straightforward option because there is no ordering information that can be used to eliminate elements.

[42, 9, 73, 18, 51, 27]

Sorted Array

A sorted array provides additional information that can be used by algorithms such as binary search.

[9, 18, 27, 42, 51, 73]

Searching for Duplicate Values

An array can contain the same value multiple times. A basic search often returns the first matching position, but some applications need every matching index.

const numbers = [10, 20, 10, 30, 10];

Target: 10

Matching indexes:
0, 2, 4

To find all occurrences, the array needs to be scanned rather than stopping after the first match.

function findAll(array, target) {
  const indexes = [];

  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      indexes.push(i);
    }
  }

  return indexes;
}

const numbers = [10, 20, 10, 30, 10];

console.log(findAll(numbers, 10));
// [0, 2, 4]

Searching for Objects in an Array

Real applications often store objects rather than primitive values. Searching then usually means checking one of the object's properties.

const users = [
  { id: 101, name: "Asha" },
  { id: 102, name: "Ravi" },
  { id: 103, name: "Maya" }
];

const user = users.find(user => user.id === 102);

console.log(user);
// { id: 102, name: "Ravi" }

Methods such as find(), findIndex(), and some() provide convenient ways to perform common searches over JavaScript arrays.

JavaScript Array Searching Methods

JavaScript provides several built-in methods for searching arrays. The appropriate method depends on what the application needs as the result.

Array Search Time Complexity

The time complexity of searching depends on the algorithm and the structure of the data.

The O(1) best case for both techniques occurs when the target is found immediately at the first comparison or at the first middle position checked by the algorithm.

What Happens When the Element Is Not Found?

A search operation should define what happens when the target does not exist. A common convention is to return -1 when searching for an index.

const numbers = [10, 20, 30];

const index = numbers.indexOf(99);

console.log(index);
// -1

For boolean existence checks, includes() can be clearer:

const numbers = [10, 20, 30];

console.log(numbers.includes(20));
// true

console.log(numbers.includes(99));
// false

Choosing the Right Array Search

There is no single searching technique that is appropriate for every array. The choice should be based on the characteristics of the data and the operation being performed.

• Use a simple sequential search when the array is unsorted.
• Use binary search when the data is sorted and repeated searches justify it.
• Use includes() when only existence needs to be checked.
• Use indexOf() when the position of a primitive value is needed.
• Use find() when an object needs to be located using a condition.
• Use findIndex() when the index of a matching object is required.

Common Array Searching Mistakes

• Using binary search on an array that does not satisfy the required ordering.
• Assuming every array search takes O(1).
• Confusing direct index access with searching for an unknown value.
• Forgetting to handle the case where the target does not exist.
• Stopping after the first match when all matching elements are required.
• Using a more complex search technique when a simple linear scan is sufficient.

Why Array Searching Matters

Searching is often the first step in a larger operation. An application may search for a record before updating it, locate an item before deleting it, or check whether a value already exists before inserting a new one.

Understanding the cost of these searches helps developers select appropriate algorithms and data structures when applications grow in size and complexity.

Key Takeaways

• Array searching finds an element or determines whether a value exists.
• Direct access by a known array index is typically O(1).
• Linear search works with both sorted and unsorted arrays.
• Binary search requires an appropriately sorted array.
• Linear search has O(n) worst-case time complexity.
• Binary search has O(log n) worst-case time complexity.
• JavaScript provides methods such as indexOf(), includes(), find(), and findIndex().
• The best search approach depends on the data and the required result.