14.first-position-of-target.cpp

//  Tag: Binary Search
//  Time: O(logN)
//  Space: O(1)
//  Ref: -
//  Note: -

//  Given a sorted array (ascending order) and a `target` number, find the first index of this number in $O(log n)$ time complexity.
//  
//  If the `target` number does not exist in the array, return `-1`.
//  
//  **Example 1:**  
//   
//  Input:  
//  ``` 
//  tuple = [1,4,4,5,7,7,8,9,9,10]
//  target = 1
//  ``` 
//  Output:  
//  ``` 
//  0
//  ``` 
//  Explanation:  
//  
//  The first index of  1 is 0.
//  
//  **Example 2:**  
//   
//  Input:  
//  ``` 
//  tuple = [1, 2, 3, 3, 4, 5, 10]
//  target = 3
//  ``` 
//  Output:  
//  ``` 
//  2
//  ``` 
//  Explanation:  
//  
//  The first index of 3 is 2.
//  
//  **Example 3:**  
//   
//  Input:  
//  ``` 
//  tuple = [1, 2, 3, 3, 4, 5, 10]
//  target = 6
//  ``` 
//  Output:  
//  ``` 
//  -1
//  ``` 
//  Explanation:  
//  
//  There is no 6 in the array，return -1.
//  
//  

class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    int binarySearch(vector<int> &nums, int target) {
        // write your code here
        int n = nums.size();
        if (n == 0) {
            return -1;
        }


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

        return nums[left] == target ? left : -1;

    }
};