Installation and Configuration
Programming Methodology

Implementing Binary Search in a Sorted Array in C++

This exercise focuses on the implementation of the binary search algorithm, which is used to efficiently find a target value within a sorted array. Binary search operates by repeatedly dividing the search interval in half and comparing the middle element with the target. If the target matches the middle element, the search is complete. If the target is less than the middle element, the search continues in the left half; otherwise, it continues in the right half. This approach significantly reduces the time complexity to O(log n), making it much faster than linear search for large datasets. You will build a function that receives a sorted array, the array size, and the value to search, then returns the index if found or -1 otherwise.

Group

Search and Sort Algorithms in C++

Objective

Write a function named binarySearch that takes a sorted array, the number of elements, and a target value to find. Inside the function, implement the binary search algorithm using a loop. In the main function, define a sorted array of integers and use the binarySearch function to locate a value. Display the result by printing the index of the element if found, or a message saying it was not found.

Develop a function that performs binary search on a sorted array.

Example C++ Exercise

 Copy C++ Code 
#include <iostream>   // Include the input-output stream library
using namespace std;

// Function to perform binary search on a sorted array
int binarySearch(int arr[], int size, int target) {
    int low = 0;               // Start index of the search range
    int high = size - 1;       // End index of the search range

    // Continue the loop while the range is valid
    while (low <= high) {
        int mid = low + (high - low) / 2;   // Calculate the middle index

        // If the element is found at mid
        if (arr[mid] == target) {
            return mid;       // Return the index where the target is found
        }
        // If the target is smaller, it lies in the left half
        else if (target < arr[mid]) {
            high = mid - 1;   // Adjust the end of the range
        }
        // If the target is larger, it lies in the right half
        else {
            low = mid + 1;    // Adjust the start of the range
        }
    }

    return -1;   // Return -1 if the target is not found
}

int main() {
    // Define a sorted array of integers
    int numbers[] = {3, 6, 9, 12, 15, 18, 21};
    int size = sizeof(numbers) / sizeof(numbers[0]);   // Calculate number of elements
    int target = 15;    // Value to search in the array

    // Call the binarySearch function
    int index = binarySearch(numbers, size, target);

    // Display the result
    if (index != -1) {
        cout << "Element found at index " << index << endl;
    } else {
        cout << "Element not found in the array." << endl;
    }

    return 0;   // Indicate successful program termination
}

 Output

Element found at index 4

Share this C++ Exercise


More C++ Programming Exercises of Search and Sort Algorithms in C++

Explore our set of C++ Programming Exercises! Specifically designed for beginners, these exercises will help you develop a solid understanding of the basics of C++. From variables and data types to control structures and simple functions, each exercise is crafted to challenge you incrementally as you build confidence in coding in C++.