Searching is one of the fundamental operations in programming. Whether you are working with arrays, strings, or matrices, knowing efficient search algorithms is essential.

In this blog, we will cover:

Linear Search
Binary Search (Iterative + Recursive)
Finding Floor & Ceil
Practice Questions (Level 1 & Level 2)

🔹 Linear Search

Linear Search iterates through the array one by one until the target is found.
It works for unsorted arrays.

const arr = [1, 2, 6, 9, 0, -5];

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

console.log(linearSearch(arr, 8)); // -1
console.log(arr.includes(9));      // true
console.log(arr.indexOf(9));       // 3
console.log(arr.find((num) => num > 0));    // 1
console.log(arr.findIndex((num) => num < 0)); // 5

⏱ Time Complexity: O(n)
⚡ Space Complexity: O(1)

🔹 Binary Search (Iterative)

Binary Search works on sorted arrays. It repeatedly divides the search space in half.

const binarySearch = (arr, target) => {
    let start = 0, end = arr.length - 1;

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);

        if (arr[mid] === target) return mid;
        else if (arr[mid] > target) end = mid - 1;
        else start = mid + 1;
    }

    return -1;
}

console.log(binarySearch([1, 4, 6, 9, 12, 15], 8)); // -1

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

🔹 Binary Search (Recursive)

Binary Search can also be implemented recursively.

const binarySearchRecursive = (arr, target) => {
    return binarySearchUtil(arr, target, 0, arr.length - 1);
}

const binarySearchUtil = (arr, target, start, end) => {
    if (start > end) return -1;

    let mid = Math.floor((start + end) / 2);

    if (arr[mid] === target) return mid;
    else if (arr[mid] > target) return binarySearchUtil(arr, target, start, mid - 1);
    else return binarySearchUtil(arr, target, mid + 1, end);
}

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(log n) (due to recursion stack)

🔹 Find Floor & Ceil in a Sorted Array

Floor: Greatest element ≤ target
Ceil: Smallest element ≥ target

const floorCeil = (arr, target) => {
    let start = 0, end = arr.length - 1;
    let floor = -1, ceil = -1;

    while (start <= end) {
        let mid = Math.floor((start + end)/2);

        if (arr[mid] === target) {
            return [arr[mid], arr[mid]]; // both floor & ceil
        }
        else if (arr[mid] > target) {
            ceil = arr[mid];
            end = mid - 1;
        }
        else {
            floor = arr[mid];
            start = mid + 1;
        }
    }

    return [ceil, floor];
}

console.log(floorCeil([1,3,5,7,9], 6)); // [7,5]

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

💻 Practice Questions

Level 1

[Sqrt(x)]
[First Bad Version]
[Find the Index of the First Occurrence in a String]
[Binary Search]
[Search Insert Position]
[Find Minimum in Rotated Sorted Array]

Level 2

[Find First and Last Position of Element in Sorted Array]
[Single Element in a Sorted Array]
[Search a 2D Matrix]
[Find Peak Element]
[Search in Rotated Sorted Array]

📝 Search Practice Question Solutions — JavaScript

Level 1

1️⃣ Sqrt(x)

Return the integer part of the square root of x.

const mySqrt = (x) => {
    if (x < 2) return x;

    let left = 1, right = x;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (mid * mid === x) return mid;
        else if (mid * mid < x) left = mid + 1;
        else right = mid - 1;
    }

    return right;
}

console.log(mySqrt(8)); // 2

⏱ Time Complexity: O(log x)
⚡ Space Complexity: O(1)

2️⃣ First Bad Version

Find the first bad version in a series using Binary Search.

const firstBadVersion = (n, isBadVersion) => {
    let left = 1, right = n;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (isBadVersion(mid)) right = mid;
        else left = mid + 1;
    }

    return left;
}

// Example usage:
// Suppose version 4 is the first bad version
const isBadVersion = (version) => version >= 4;
console.log(firstBadVersion(10, isBadVersion)); // 4

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

3️⃣ Find the Index of the First Occurrence in a String

const strStr = (haystack, needle) => {
    if (needle === "") return 0;
    return haystack.indexOf(needle);
}

console.log(strStr("hello", "ll")); // 2
console.log(strStr("aaaaa", "bba")); // -1

⏱ Time Complexity: O(n*m) (n = haystack length, m = needle length)
⚡ Space Complexity: O(1)

4️⃣ Binary Search

const binarySearch = (nums, target) => {
    let left = 0, right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

console.log(binarySearch([1,3,5,6], 5)); // 2

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

5️⃣ Search Insert Position

const searchInsert = (nums, target) => {
    let left = 0, right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return left;
}

console.log(searchInsert([1,3,5,6], 5)); // 2
console.log(searchInsert([1,3,5,6], 2)); // 1

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

6️⃣ Find Minimum in Rotated Sorted Array

const findMin = (nums) => {
    let left = 0, right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) left = mid + 1;
        else right = mid;
    }

    return nums[left];
}

console.log(findMin([3,4,5,1,2])); // 1

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

Level 2

1️⃣ Find First and Last Position of Element in Sorted Array

const searchRange = (nums, target) => {
    const findBound = (isFirst) => {
        let left = 0, right = nums.length - 1, bound = -1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (nums[mid] === target) {
                bound = mid;
                if (isFirst) right = mid - 1;
                else left = mid + 1;
            } else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return bound;
    }

    return [findBound(true), findBound(false)];
}

console.log(searchRange([5,7,7,8,8,10], 8)); // [3,4]

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

2️⃣ Single Element in a Sorted Array

const singleNonDuplicate = (nums) => {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (mid % 2 === 1) mid--; // make mid even
        if (nums[mid] === nums[mid + 1]) left = mid + 2;
        else right = mid;
    }
    return nums[left];
}

console.log(singleNonDuplicate([1,1,2,3,3,4,4,8,8])); // 2

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

3️⃣ Search a 2D Matrix

const searchMatrix = (matrix, target) => {
    if (!matrix.length) return false;
    const rows = matrix.length, cols = matrix[0].length;
    let left = 0, right = rows * cols - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midVal = matrix[Math.floor(mid/cols)][mid % cols];
        if (midVal === target) return true;
        else if (midVal < target) left = mid + 1;
        else right = mid - 1;
    }

    return false;
}

console.log(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3)); // true

⏱ Time Complexity: O(log(m*n))
⚡ Space Complexity: O(1)

4️⃣ Find Peak Element

const findPeakElement = (nums) => {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] < nums[mid + 1]) left = mid + 1;
        else right = mid;
    }
    return left;
}

console.log(findPeakElement([1,2,3,1])); // 2

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

5️⃣ Search in Rotated Sorted Array

const searchRotated = (nums, target) => {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right)/2);
        if (nums[mid] === target) return mid;

        if (nums[left] <= nums[mid]) { // left sorted
            if (target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else { // right sorted
            if (target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

console.log(searchRotated([4,5,6,7,0,1,2], 0)); // 4

⏱ Time Complexity: O(log n)
⚡ Space Complexity: O(1)

✅ Summary

Level 1: Basic Binary Search problems
Level 2: Advanced Binary Search variations (rotated arrays, 2D matrices, peaks)
Use Binary Search wherever the array is sorted or partially sorted.
Recursive Binary Search is elegant but iterative is more memory-efficient.

🎯 Key Takeaways

Linear Search: Simple, works for unsorted arrays.
Binary Search: Efficient, only for sorted arrays.
Recursive Binary Search: Elegant, uses stack memory.
Floor & Ceil: Useful for range queries and nearest elements.

🔍 Searching Algorithms in JavaScript — Complete Guide

🔹 Linear Search

🔹 Binary Search (Iterative)

🔹 Binary Search (Recursive)

🔹 Find Floor & Ceil in a Sorted Array

💻 Practice Questions

Level 1

Level 2

📝 Search Practice Question Solutions — JavaScript

Level 1

1️⃣ Sqrt(x)

2️⃣ First Bad Version

3️⃣ Find the Index of the First Occurrence in a String

4️⃣ Binary Search

5️⃣ Search Insert Position

6️⃣ Find Minimum in Rotated Sorted Array

Level 2

1️⃣ Find First and Last Position of Element in Sorted Array

2️⃣ Single Element in a Sorted Array

3️⃣ Search a 2D Matrix

4️⃣ Find Peak Element

5️⃣ Search in Rotated Sorted Array

✅ Summary

🎯 Key Takeaways

Comments

More from this blog

🔐 bcrypt.js in Node.js

Lucide React Setup Guide

🌐 CORS Setup in MERN Project

⚛️ React Hooks: The Complete Guide for Modern React Developers

🌐 React Context API: The Complete Guide to Managing Global State

Command Palette

🔹 Linear Search

🔹 Binary Search (Iterative)

🔹 Binary Search (Recursive)

🔹 Find Floor & Ceil in a Sorted Array

💻 Practice Questions

Level 1

Level 2

📝 Search Practice Question Solutions — JavaScript

Level 1

1️⃣ Sqrt(x)

2️⃣ First Bad Version

3️⃣ Find the Index of the First Occurrence in a String

4️⃣ Binary Search

5️⃣ Search Insert Position

6️⃣ Find Minimum in Rotated Sorted Array

Level 2

1️⃣ Find First and Last Position of Element in Sorted Array

2️⃣ Single Element in a Sorted Array

3️⃣ Search a 2D Matrix

4️⃣ Find Peak Element

5️⃣ Search in Rotated Sorted Array

✅ Summary

🎯 Key Takeaways

Comments

More from this blog