704.binary-search.cpp

/*
 * @lc app=leetcode id=704 lang=cpp
 *
 * [704] Binary Search
 *
 * https://leetcode.com/problems/binary-search/description/
 *
 * algorithms
 * Easy (48.54%)
 * Total Accepted:    60.3K
 * Total Submissions: 124.2K
 * Testcase Example:  '[-1,0,3,5,9,12]\n9'
 *
 * Given a sorted (in ascending order) integer array nums of n elements and a
 * target value, 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
 * 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
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * You may assume that all elements in nums are unique.
 * n will be in the range [1, 10000].
 * The value of each element in nums will be in the range [-9999, 9999].
 * 
 * 
 */
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int pos = -1;
        int n = nums.size();
        if(n == 0)  return -1;

        for(int k = n; k>=1; k/=2){
            while(pos+k<n && nums[pos+k]<=target)
                pos += k;
        }
        if(pos>=0 && nums[pos] == target)
            return pos;
        return -1;
    }
};