Binary Search as Divide and Conquer in DSA Typescript - Build from Scratch

Binary Search as Divide and Conquer

📖 Scenario: You have a sorted list of numbers representing the floors of a building where a special event is happening. You want to quickly find if a certain floor number is part of this list.

🎯 Goal: Build a binary search function using divide and conquer to find if a floor number exists in the sorted list.

📋 What You'll Learn

Create a sorted array called floors with the exact values: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Create a variable called targetFloor and set it to 14

Write a function called binarySearch that takes arr, target, start, and end as parameters and uses divide and conquer to find the target

Call binarySearch with floors, targetFloor, 0, and floors.length - 1

Print the result of the binary search function

💡 Why This Matters

🌍 Real World

Binary search is used in many real-world applications like searching in phone books, dictionaries, or any sorted data quickly.

💼 Career

Understanding binary search is fundamental for software developers and engineers to write efficient search algorithms and optimize performance.

1

Create the sorted array of floors

Create a sorted array called floors with these exact values: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

DSA Typescript

# Your code here

Hint

Use const floors = [...] to create the array with the exact numbers.

2

Set the target floor to search

Create a variable called targetFloor and set it to 14

DSA Typescript

const floors = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
# Your code here

Hint

Use const targetFloor = 14; to set the floor you want to find.

3

Write the binary search function

Write a function called binarySearch that takes arr, target, start, and end as parameters and uses divide and conquer to find the target. It should return the index of the target if found, or -1 if not found.

DSA Typescript

const floors = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
const targetFloor = 14;

# Your code here

Hint

Use recursion to divide the array and check the middle element each time.

4

Call the function and print the result

Call binarySearch with floors, targetFloor, 0, and floors.length - 1. Print the result using console.log.

DSA Typescript

const floors = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
const targetFloor = 14;

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

# Your code here

Hint

Call the function with the full array range and print the returned index.