14. First Position of Target

做题历程：

1. 本题应该是第一次做，本次耗时10分钟左右，独立解出

本题其实还比较简单，基本靠Binary Search模板就能搞定，不过这里还是得说一下里面三个case

1. array[middle] < target，此时可以放心大胆的start = middle + 1
2. array[middle] == target, 此时要小心，因为不能排除这个点，所以要end = middle
3. array[middle] > target, 此时可以放心大胆end = middle - 1

而且要注意while loop的条件是start + 1 < end，即首尾相邻就退出。。。当然，这样退出循环后就要先检查start，再检查end

代码如下：

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
        int start = 0;
        int end = array.size() - 1;
        while (start + 1 < end) {
            int middle = start + (end - start) / 2;
            if (array[middle] < target) {
                start = middle + 1;
            }
            else if (array[middle] == target) {
                end = middle;
            }
            else {
                // array[middle] > target
                end = middle - 1;
            }
        }
        if (array[start] == target) {
            return start;
        }
        if (array[end] == target) {
            return end;
        }
        return -1;
    }
};