main.cpp

// Source: https://leetcode.com/problems/binary-search
// Title: Binary Search
// Difficulty: Easy
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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`.
//
// You must write an algorithm with `O(log n)` runtime complexity.
//
// **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 <= 10^4`
// - `-10^4 < nums[i], target < 10^4`
// - All the integers in `nums` are **unique**.
// - `nums` is sorted in ascending order.
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <vector>

using namespace std;

// Binary Search
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int n = nums.size();

    // nums[lo-1] < target, nums[hi] > target
    auto lo = 0, hi = n;
    while (lo < hi) {
      auto mid = lo + (hi - lo) / 2;
      if (nums[mid] == target) return mid;
      if (nums[mid] < target) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    return -1;
  }
};