Search Sorted Array - C++ Solution

1. Introduction

In this post, we'll discuss a fundamental algorithm in computer science - binary search. The challenge is to implement an efficient search algorithm that operates in logarithmic time complexity, making it highly efficient for large datasets.

Problem

Given a sorted array of integers and a target value, the task is to determine if the target exists in the array. If it does, return the index where it is found. In the presence of duplicates, any index with the target value is acceptable. If the target is not found, return -1.

2. Solution Steps

1. Implement a binary search algorithm.

2. Start with the middle element of the array.

3. If the target is equal to the middle element, return its index.

4. If the target is less than the middle element, search the left half of the array.

5. If the target is more than the middle element, search the right half of the array.

6. Repeat steps 2-5 until the target is found or the subarray reduces to zero length.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to perform binary search
int binarySearch(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoiding overflow

        // Check if target is present at mid
        if (nums[mid] == target) {
            return mid; // Target found
        }

        // If target is greater, ignore left half
        if (nums[mid] < target) {
            left = mid + 1;
        }
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }

    // Target not found
    return -1;
}

int main() {
    vector<int> nums = {2, 3, 5, 7, 9};
    int target = 7;
    cout << "Index of " << target << ": " << binarySearch(nums, target) << endl;
    return 0;
}

Output:

Index of 7: 3

Explanation:

The function binarySearch uses binary search to find the index of a target in a sorted array. It divides the search interval in half repeatedly, reducing the search space logarithmically. For the input array [2, 3, 5, 7, 9] with target 7, the output is 3, indicating that 7 is found at the 4th position (index 3). In cases where the target is not found, the function returns -1.