public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

2.四种二分查找变体

(1)查找第一个值等于给定值的元素

(2)查找最后一个值等于给定值的元素

(3)查找第一个大于等于给定值的元素

(4)查找最后一个小于等于给定值的元素

3.二分查找实现场景

---

(1)如何在1000万个整数中快速查找某个整数？

    设内存限制是100MB，每个数据⼤⼩是8字节，最简单的办法就是将数据存储在数组中，内存占⽤差不多是80MB，符合内存的限制。

    可以先对这1000万数据从⼩到⼤排序，然后再利⽤⼆分查找算法，就可以快速地查找想要的数据了。

     eg. 为什么不用 散列表和二叉树？

    如果⽤散列表或者⼆叉树来存储这1000万的数据， 每个节点除了存储数据还要存储邻居或子节点引用关系。⽽ ⼆分查找底层依赖的是数组，除了数据本身之外，不需要额外存储其他信息，是最省内存空间的存储⽅式。

(2)如何快速定位IP地址的归属地？

     问题： 查询202.102.133.13 IP地址的归属地时，在地址库中搜索，发现这个IP地址落在[202.102.133.0, 202.102.133.255]这个地址范围内，其归属地为“山东东营市”。

    

    方法： 如果IP区间与归属地的对应关系不经常更新，我们可以先预处理这12万条数据，让其按照起始IP从⼩到⼤排序（IP地址可以转化为32位的整型数）。

    查找过程=“ 在有序数组中，查找最后一个小于等于某个给定值的元素 ”。

     当我们要查询某个IP归属地时，我们可以先通过二分查找，找到最后一个起始IP小于等于这个IP的IP区间，然后，检查这个IP是否在这个IP区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到。