Lintcode: Binary Search

For a given sorted array (ascending order) and a targetnumber, 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.

Have you met this question in a real interview? 

Yes

Example

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Challenge

If the count of numbers is bigger than 2^32, can your code work properly?

Tags Expand 

Binary Search Array

Note repetitive elements! The returned index has to be the first element equals to target.
So I cannot just use the format used before, which just return the first element that more than target.
I need to change the if condition so that when loops end, start points to the first element that more and equal to target.
p.s. considering the number of elements in the array, we use long int to store indexes.
Time: O(logn)
Space: O(1)

class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target number to find.
     * @return: The first position of target. Position starts from 0. 
     */
    int binarySearch(vector<int> &array, int target) {
        // write your code here
        long int start = 0;
        long int end = array.size() - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(array[mid] >= target) end = mid - 1;
            if(array[mid] < target) start = mid + 1;

        }
        if(array[start] == target) return start;
        return -1;
    }
};