二分查找

二分查找又叫折半查找

　　优点是比较的次数少,查找速度快,平均性能好

　　缺点是要求查找的列表为有序的(上升或者下降)

　　查找思路是 (1)首先记录列表中间位置的关键字与要查找的关键字比较,如果两者相等,则证明查找成功;

　　　　　　　 (2)如果两个关键字不相等,首先将列表以中间位置关键字分成前后两个子列表,如果带查找关键字大于中间位置关键字,则查找后一子列表,反之查找前一字表.

　　　　　　　 (3)重复以上过程,直到查找成功,或者直到子表不存在,此时查找不成功.

　　JAVA代码实现

 1 /**
 2      * 二分法 java实现
 3      * 
 4      * @param sourceArray
 5      * @param target
 6      * @return
 7      */
 8     public static int binarySearch(Integer[] sourceArray, int target) {
 9         int low = 0;
10         int high = sourceArray.length - 1;
11 
12         while ((low <= high) && (low <= sourceArray.length - 1)
13                 && (high <= sourceArray.length - 1)) {
14             int middle = low + ((high - low) >> 1);    //二分查找算法精华
15             if (target == sourceArray[middle]) {
16                 return middle;
17             } else if (target < sourceArray[middle]) {
18                 high = middle - 1;
19             } else {
20                 low = middle + 1;
21             }
22         }
23         return -1;
24     }

　　解释:

　　　　　int middle = low + ((high - low)>>1);

　　　　　这段代码的意思是找到一个数的中间位置,>>的意思为右移,1是右移一位.

　　　　　例子:

　　　　　　　　15 >> 2 这里将15的十进制---->二进制解释

　　　　　　　　15的十进制是00001111 如何算:

　　　　　　　　15÷2 = 7 余1　　↑得出

　　　　　　　　 7÷2 = 3 余1　　↑逆向

　　　　　　　　 3÷2 = 1 余1　　↑向上

　　　　　　　　 1÷2 = 0 余1　　↑这里

　　　　　　　　由于位数不够,这里要补位加了4个0,所以得出0000 1111

　　　　　　　　0000 1111向右移2位得出 0000 0011, 将0000 0011转换十进制, 如何转换

　　　　　　　　0 0 0 0 0 0 1 1 二进制源数据　　

　　　　　　　 7 6 5 4 3 2 1 0 下标

　　　　　　　　(0*2^7) + (0*2^6) + (0*2^5) + (0*2^4) + (0*2^3) + (0*2^2) + (1*2^1) + (1*2^0) = 3;

　　　　　　　　解释:二进制转换到十进制,比如下标是1 , 那就是2的1次方乘 1( 1 代表二进制源数据) ,

　　　　　　　　得出 15 >> 2 = 3

　　　　如有错误,欢迎指正