Java 实现二分法回忆片段和解决方案。

今天突然就非常怀念在我的第一份工作的时候, 我们的老大曾经出了一道题: 实现二分法算法. 这道题直到现在对我的影响依然很大. 其实说了这么多, 大家肯定会说这谁不会写啊, 结果写出来的往往就踩了那么几个坑
首先让我们思考一个简单的问题: 什么样的情况适合使用二分查找法?
数组的值从小到大有序排列. 如果别人给你数组你就写也不问一下, 那是不是代表你在工作中也常常先动手后思考呢：）
那么开始动手实现吧, 已知数组有序

/**
 *
 * @param demo 有序数组
 * @param key 待查找元素
 * @return 返回查找元素的数组下标
 */
public int binarySearch(int[] demo, int key) {
    if(null==demo) {
        return -1;
    }

    int left=0;
    int right=demo.length-1;

    while(left<=right) {
        int mid=left+(right-left)/2;

        if(demo[mid]<key) {
            left=mid+1;
        } else if(demo[mid]>key){
            right=mid-1;
        } else {
            return mid;
        }
    }

    return -left-1;
}

总结一下这几个容易让人忽视的坑吧;)

1. 方法入口处的边界值判断
2. mid值求法避免溢出
3. 重复值处理, 上面的方法没有处理重复数字情况, 要根据实际需要来修改
   后续:
   其实jdk的源码是这样处理mid求和除以2的

   int mid = (left + right) >>> 1;
   

   java常用不不常用的计算符号
   1、左移( « )
   2、右移( » )
   3、无符号右移( »> )
   我们知道在Java中int类型占32位, 可以表示一个正数, 也可以表示一个负数。正数换算成二进制后的最高位为0, 负数的二进制最高为为1
   通过其结果转换成二进制后, 我们可以发现, 正数右移, 高位用0补, 负数右移, 高位用1补, 当负数使用无符号右移时, 用0进行部位(自然而然的, 就由负数变成了正数了) 注意：笔者在这里说的是右移, 高位补位的情况。正数或者负数左移, 低位都是用0补。
   4、位与( & )
   位与：第一个操作数的的第n位于第二个操作数的第n位如果都是1, 那么结果的第n为也为1, 否则为0
   5、位或( | )
   位或操作：第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1, 那么结果的第n为也为1, 否则为0
   6、位异或( ^ )
   位异或：第一个操作数的的第n位于第二个操作数的第n位 相反, 那么结果的第n为也为1, 否则为0
   7、位非( ~ ) 位非是一元操作符
   位非：操作数的第n位为1, 那么结果的第n位为0, 反之。