二分法

传统的二分查找模板的问题

• 尽量使用int mid=left+（right-left）>>1;
• 循环可以进行的条件写成while（left<=right），在退出循环的时候，需要考虑返回left还是right

二分查找模板的基本思想

• 首先把循环进行的条件写成while（left<right），这样退出的时候，一定有left==right成立，此时left和right返回都行。这个时候由于退出的那个值可能没有检查，所以需要额外检查一下

细节、注意事项、调试方式

• 前提：思考左右边界，如果左右边界不包括目标数值，会导致错误结果
• 中位数先写成和移位的形式；然后根据循环里分支的编写情况做调整；当数组的元素个数是偶数时
  左中位数：left+（right-left）>>1;
  右中位数：left+（right-left+1）>>1;
  当元素个数为奇数时，上述表达式结果均为中位数
• 先写逻辑上容易得到的分支（排除一定是的或者一定不是的），这个逻辑通常是排除中位数的逻辑
• 循环内只写两个分支：排除中位数的逻辑和反之
• 根据分支类型，选择中位数的类型，左中位数或者右，选择的标准是避免死循环
• 退出循环的时候，可能需要对夹逼剩下的元素单独判断一次，这一步叫做后处理
• 取中位数避免整形溢出