Problem Statement

Given a sorted array of integers nums with 0-based indexing, find the index of a specified target integer. If the target is found in the array, return its index. If the target is not found, return -1.

Examples

Example 1:

Input: nums = [-1, 0, 1, 5, 7, 9], target = 7
Output: 4

Explanation: The target element 7 is present at index 4 in the array.

Example 2:

Input: nums = [0, 1, 2, 3, 4, 4, 5], target = 4
Output: 4

Explanation: There are two occurrences of the element 4,
However the first occurrence is at index 4.

Different Approach

Intuition:

Since the array is sorted, we can efficiently search for the element using Binary Search. Binary search works by repeatedly dividing the search space into halves. We compare the middle element of the current search space with x:

• If the middle element equals x, we return the index.
• If x is smaller than the middle element, we discard the right half and continue searching in the left half.
• If x is larger than the middle element, we discard the left half and continue searching in the right half.

This process continues until either the element is found or the search space is exhausted.

1️⃣ Iterative Approach

Algorithm (Iterative Approach):

1. Set left = 0 and right = n - 1.
2. While left <= right:
   • Compute the middle index: mid = left + (right - left) / 2.
   • If arr[mid] == x, return mid (element found).
   • If arr[mid] > x, set right = mid - 1 (search in the left half).
   • If arr[mid] < x, set left = mid + 1 (search in the right half).
3. If x is not found, return -1.

Dry Run:

Target = 9
        +-----+-----+-----+-----+-----+-----+
arr[] = |  1  |  3  |  5  |  7  |  9  | 11  |
        +-----+-----+-----+-----+-----+-----+
           0     1     2     3     4     5
           

left = 0
right = 5

First Iteration:

Target = 9

left = 0
right = 5

mid = left + (right - left) / 2
    = 0 + (5 - 0) / 2 = 5 / 2 = 2

        +-----+-----+-----+-----+-----+-----+
arr[] = |  1  |  3  |  5  |  7  |  9  | 11  |
        +-----+-----+-----+-----+-----+-----+
           0     1     2     3     4     5
           ^           ^                 ^
           |           |                 |
         left         mid               right

since arr[mid]  < target
      2 < 9
      set left = mid + 1

Second Iteration:

Target = 9

left = 3
right = 5

mid = left + (right - left) / 2
    = 3 + (5 - 3) / 2 = 3 + 2 / 2 = 3 + 1 = 4

        +-----+-----+-----+-----+-----+-----+
arr[] = |  1  |  3  |  5  |  7  |  9  | 11  |
        +-----+-----+-----+-----+-----+-----+
           0     1     2     3     4     5
           ^                       ^     ^
           |                       |     |
         left                     mid  right

since arr[mid]  == target
      9 == 9
      return mid index.

Code:

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

int binarySearchIterative(const vector<int>& arr, int x) {
    int left = 0, right = arr.size() - 1;

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

        if (arr[mid] == x)
            return mid;  // Element found
        else if (arr[mid] < x)
            left = mid + 1;  // Search the right half
        else
            right = mid - 1;  // Search the left half
    }

    return -1;  // Element not found
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int x = 9;
    
    int index = binarySearchIterative(arr, x);
    if (index != -1)
        cout << "Element found at index " << index << endl;
    else
        cout << "Element not found" << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:

  • Both the iterative and recursive approaches perform a binary search in O(log n) time, as the search space is halved in each iteration/recursion.
    • Best Case: O(1) when the element is found at the middle.
    • Worst Case: O(log n) when the element is not present or is at the extremes of the array.
• Space Complexity:
  • Iterative Approach: O(1) as only a few extra variables are used.

2️⃣ Recursive Approach

Code:

#include <iostream>
using namespace std;

int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;
        
        // Base case: target found
        if (arr[mid] == target)
            return mid;
        // If target is smaller, search in the left half
        else if (arr[mid] > target)
            return binarySearchRecursive(arr, left, mid - 1, target);
        // If target is larger, search in the right half
        else
            return binarySearchRecursive(arr, mid + 1, right, target);
    }
    
    // Target not found
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 8;
    
    int result = binarySearchRecursive(arr, 0, n - 1, target);
    if (result != -1)
        cout << "Element found at index " << result << endl;
    else
        cout << "Element not found" << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(log n), where n is the number of elements.
  • Because the array is divided in half at each step.
• Space Complexity:O(log n), where n is the number of elements.
  • Because the recursion stack used for each function call.