Binary Search

Problem Statement

Given the problem description, the task is to perform a search operation. Specifically, you must create a function to find a specified integer, referred to as target, within an array of integers named nums. It is essential to note that this array is already sorted in ascending order. The function should return the index of the target if it exists within nums or -1 if it does not appear in the array.

The challenge is to achieve this with an algorithm that has a time complexity of O(log n), suggesting the necessity of using an efficient algorithm capable of handling potentially large input sizes as the length of the array can go up to 10,000 elements.

Examples

Example 1

Input:

nums = [-1,0,3,5,9,12], target = 9

Output:

4

Explanation:

9 exists in nums and its index is 4

Example 2

Input:

nums = [-1,0,3,5,9,12], target = 2

Output:

-1

Explanation:

2 does not exist in nums so return -1

Constraints

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

Approach and Intuition

The given problem is searching an element in a sorted array, which implies that binary search is ideal due to its O(log n) complexity. Here’s how the solution can be structured using binary search:

1. Start with initializing two pointers, left (beginning of the array) and right (end of the array).
2. Enter a loop where left is less than or equal to right.
3. Find the middle element of the array using the average of left and right (integer divide by 2).
4. Compare this middle element with the target.
   • If they are the same, the middle index is returned, signaling that target has been found.
   • If the target is smaller than the middle element, adjust the right pointer to mid - 1 as this indicates that if target is in nums, it lies to the left of mid.
   • If the target is larger than the middle element, adjust the left pointer to mid + 1, since this implies target would be in the right half of the array.
5. If the loop exits without finding the target, return -1 as this indicates that target is not present in the array.

• Example based on Approach:
  • For nums = [-1,0,3,5,9,12] and target = 9, initialize left = 0 and right = 5.
  • Calculate mid as (0 + 5) // 2 = 2, which corresponds to nums[2] = 3. Since 9 > 3, adjust left to 3.
  • Recalculate mid as (3 + 5) // 2 = 4, giving nums[4] = 9, which matches target. Return index 4.

By following the steps outlined, a clear, efficient, and systematically reducing search area approach guarantees the O(log n) complexity, making optimal use of the sorted nature of the array.

Solutions

class Solution {
public:
    int findIndex(vector<int>& data, int goal) {
        int low = 0, high = int(data.size());
            
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (data[middle] >= goal) {
                high = middle;
            } else {
                low = middle + 1;
            }
        }
            
        if (low < data.size() && data[low] == goal) {
            return low;
        } else {
            return -1;
        }
    }
};