Binary Search Recursive Approach in DSA Typescript - Build from Scratch

Binary Search Recursive Approach

📖 Scenario: You have a sorted list of numbers representing book IDs in a library. You want to find if a specific book ID exists using a fast method.

🎯 Goal: Build a recursive binary search function in TypeScript to find a book ID in the sorted list.

📋 What You'll Learn

Create a sorted array of book IDs

Set the target book ID to search for

Write a recursive binary search function

Print the index of the found book ID or -1 if not found

💡 Why This Matters

🌍 Real World

Binary search is used in many software systems to quickly find items in sorted lists, such as searching for a book in a library database or looking up a contact in a phone book.

💼 Career

Understanding binary search and recursion is fundamental for software developers, especially when working with algorithms that require efficient searching and data handling.

1

Create the sorted array of book IDs

Create a variable called bookIDs and assign it the sorted array [101, 203, 305, 407, 509, 611, 713].

DSA Typescript

# Your code here

Hint

Use const to create the array with the exact numbers in order.

2

Set the target book ID to search

Create a variable called targetID and set it to 407.

DSA Typescript

const bookIDs = [101, 203, 305, 407, 509, 611, 713];
# Your code here

Hint

Use const to create the target ID variable with the exact value.

3

Write the recursive binary search function

Write a recursive function called binarySearch that takes parameters arr, target, left, and right. Use the middle index to compare and recursively search the left or right half. Return the index if found, otherwise return -1.

DSA Typescript

const bookIDs = [101, 203, 305, 407, 509, 611, 713];
const targetID = 407;

# Your code here

Hint

Use Math.floor to find the middle index. Compare arr[mid] with target. Call binarySearch recursively on the left or right half.

4

Print the search result

Call binarySearch with bookIDs, targetID, 0, and bookIDs.length - 1. Print the returned index using console.log.

DSA Typescript

const bookIDs = [101, 203, 305, 407, 509, 611, 713];
const targetID = 407;

function binarySearch(arr: number[], target: number, left: number, right: number): number {
    if (left > right) {
        return -1;
    }
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

# Your code here

Hint

Call binarySearch with the full array range and print the result.