704_binary_search.cpp

/*
LeetCode 704 - Binary Search
Difficulty: Easy

Problem:
Given an array of integers nums which is sorted in ascending order, and an integer target,
write a function to search target in nums. If target exists, then return its index.
Otherwise, return -1.

Example 1:
    Input: nums = [-1,0,3,5,9,12], target = 9
    Output: 4

Example 2:
    Input: nums = [-1,0,3,5,9,12], target = 2
    Output: -1

Constraints:
    1 <= nums.length <= 10^4
    -10^4 < nums[i], target < 10^4
    All the integers in nums are unique.
    nums is sorted in ascending order.

Time Complexity: O(log n)
Space Complexity: O(1)
*/

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

int main() {
    Solution solution;

    vector<int> nums1 = {-1, 0, 3, 5, 9, 12};
    cout << solution.search(nums1, 9) << endl;  // 4

    vector<int> nums2 = {-1, 0, 3, 5, 9, 12};
    cout << solution.search(nums2, 2) << endl;  // -1

    return 0;
}