前两天阅读SparseArray时看到里面查找数组中是否已经包含某key时使用了binary search方法，其中还使用了一些位操作，今天简单分析一下
wiki 图示：(Link)
binary search wiki pic.png
Android中util.ContainerHelpers中的实现api：
binary search.png
排序前提：array本身已为有序数组
查找过程：
0.向右无符号移位1位，得到middle位值；
1.以mid为准比对midIndex位置值与参数value大小，大则hi位移至现mid位前一位，小则lo位移至现mid位后一位，相等则返回mid；
2.重复以上过程直至不满足循环条件或是又查找结果
从low、high可以看出，结果返回的是value在数组中对应的index，如果为负则代表不存在（最后一行，返回~lo会得到一个负数，因为lo计算结果一定为正，个人感觉直接返回一个负数可以连按位取反都省略掉，是不是性能更优？）
Java 位操作符：
Java bit calculate.png
识别二维码，关注公众号“夕识”
夕识.jpeg
网友评论