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

Binary Search as Divide and Conquer

📖 Scenario: You have a sorted list of book page numbers where a special note is hidden. You want to find the page number quickly using a method that splits the search area in half each time.

🎯 Goal: Build a C program that uses binary search to find a target page number in a sorted array of page numbers.

📋 What You'll Learn

Create a sorted array of integers called pages with the exact values: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91

Create an integer variable called target and set it to 23

Write a function called binary_search that takes the array, its size, and the target, and returns the index of the target or -1 if not found

Print the index returned by binary_search

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding binary search helps in optimizing search operations in software development, improving performance in data retrieval tasks.

1

Create the sorted array of page numbers

Create an integer array called pages with these exact values: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91.

DSA C

# Create the array pages with the given values
// Your code here

Hint

Use int pages[] = { ... }; to create the array with the exact numbers.

2

Set the target page number

Create an integer variable called target and set it to 23 inside the main function.

DSA C

#include 

int pages[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

int main() {
    // Create target variable and set to 23
    // Your code here
    return 0;
}

Hint

Inside main, write int target = 23;.

3

Write the binary search function

Write a function called binary_search that takes int arr[], int size, and int target as parameters. Use a divide and conquer approach with low, high, and mid variables to find the target. Return the index if found, or -1 if not found.

DSA C

#include 

int pages[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

// Write binary_search function here
// Your code here

int main() {
    int target = 23;
    return 0;
}

Hint

Use a while loop with low and high to narrow down the search. Calculate mid and compare arr[mid] with target.

4

Call binary_search and print the result

Call binary_search with pages, its size 10, and target. Store the result in an integer variable called index. Then print index using printf.

DSA C

#include 

int pages[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

int binary_search(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    int target = 23;
    // Call binary_search and print the index
    // Your code here
    return 0;
}

Hint

Call binary_search(pages, 10, target), save to index, then print index with printf("%d\n", index);.