数据结构之二分查找

二分查找（Binary Search）算法，也叫折半查找算法，当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法，二分查找是针对有序数据集合的查找算法，二分查找是针对有序数据集合的查找算法，如果是无序数据集合就遍历查找

image.png

本质

二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。
一个有序的数组中查找某个数字是否存在

package com.david.alth.half;

/**
 *二分法标准
 */
 public class HalfDemo1 {
     public static int binarySearch(int[] nums, int t) {
         //低位索引
         int low = 0;
         //高位索引
         int high = nums.length - 1;
         //中间索引
         int mid = 0;

         while (low <= high) {
             mid = (low + high) / 2;
             //等于半数
             if (t == nums[mid]) {
                 return mid;
             }
             //半数以里
             else if(t < nums[mids]) {
                 high = mid - 1;
             }
             //半数以外
             else {
                 low = mid + 1;
             }
         }

         return -1;
     }

     public static void main(String[] args) {
         //有序数组
         int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82};
         System.out.println(binarySearch(nums, 66));
     }
 }

 /*
 * 递归实现
 */
 public int bsearch(int[] a, int n, int val) {
     return bsearchInternally(a, 0, n - 1, val);
 }

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

经典案例

一个有序数组有一个数出现1次，其他数出现2次，找出出现一次的数
比如：1 1 2 2 3 3 4 4 5 5 6 6 7 出现1次的数是7
暴力：
O(n)
hash：
O(n)
关键：时间复杂度 O(logn)
思路：
使用二分查找： 1 有序、 2、时间复杂度 O(logn)
偶数位索引跟后面的比相同，奇数位索引跟前面的比相同 则说明前面的都对
偶数位索引跟前面的比相同，奇数位索引跟后面的比相同 则说明后面的都对

package com.david.alth.half;

public class HalfDemo2 {
    public static int binarySearch(int[] nums) {
        //低位索引
        int low = 0；
        //高位索引
        int high = nums.length - 1;
        //中间索引
        int mid = 0;

        while (low <= high) {
            mid = (low + high) / 2;
            //偶数位
            if(mid % 2 == 0) {
                //与后面的数相等
                if (nums[mid] == nums[mid + 1]) {
                    //前面的都对
                    low = mid + 1;
                }
                //与前面的数相等
                else if (nums[mid] == nums[mid - 1]) {
                    //后面的都对
                    high = mid - 1;
                }
                //就是这个数
                else {
                    return nums[mid];
                }
            }
            //奇数位
            else {
                //与前面的数相等
                if (nums[mid] == nums[mid - 1]) {
                    //前面的都对
                    low = mid + 1;
                }
                //与后面的数相等
                else if (nums[mid] == nums[mid + 1]) {
                    //后面的都对
                    high = mid - 1;
                } else {
                    return nums[mid];
                }
            }
        }
        //low=high
        return nums[low]; 
    }


    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 4, 4, 5, 5};
        System.out.println(binarySearch(nums));
    }
}

时间复杂度

时间复杂度就是 O(logn)

优缺点

优点：速度快，不占空间，不开辟新空间
缺点：必须是有序的数组，数据量太小没有意义，但数据量也不能太大，因为数组要占用连续空间

应用

有序的查找都可以使用二分法。
如何快速定位出一个IP地址的归属地？
如果IP区间与归属地的对应关系不经常更新，我们可用先预处理这12万条数据，让其按照起始IP从小到大排序。如何来排序呢？我们知道，IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。
当我们要查询某个IP归属地时，我们可以先通过二分查找，找到最后一个起始 IP 小于等于这个IP的IP区间，然后，检查这个 IP 是否在这个 IP 区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到。