• 对未给边界的big array：倍增法，mid不是/2而是*2，直到找到边界，然后进行正常二分
• 二分答案：通常未给数组和明显的start，end边界，需要自己确定边界

二分法的精髓是排除不可能&选取可能的一半，边界，选取条件都要根据不同题目取值 要优化O(n) 基本都是用二分法

思考模板：

int binarySearch(vector<int>& nums, int target) {
    if (nums.size == 0) return -1;
    int start = 0, end = nums.size-1;
    while (start+1 < end){//相邻则退出
        int mid = start+(end-start)/2;//防止溢出
        if (nums[mid] == target) {
          start = mid; //这里要根据题意判断是start=mid还是end=mid或者直接return mid
        }
        else if (nums[mid] < target) {
          start = mid;
        }
        else {
          end = mid;
        }        
    }
    if (nums[start] == target) {//这里要根据题意判断先返回start还是end
        return start;
    }
    if (nums[end] == target) {
        return end;
    }
}

Keypoints：

• 对输入做异常处理：数组为空或者数组长度为0。
• int mid = start + (end - start) / 2 这种表示方法可以防止两个整型值相加时溢出。
• Recursion or While-Loop：使用迭代而不是递归进行二分查找，因为工程中递归写法存在潜在溢出的可能
• while循环终止条件：while终止条件应为start + 1 < end而不是start <= end，start == end时可能出现死循环，即循环终止条件是相邻或相交元素时退出。配合while终止条件start + 1 < end（相邻即退出）的赋值语句mid永远没有+1或者-1，这样不会死循环。
• 迭代终止时target应为start或者end中的一个。循环终止条件有两个，具体应看是找第一个还是最后一个而定。