美文网首页
数据结构之二分查找

数据结构之二分查找

作者: david161 | 来源:发表于2022-05-01 07:01 被阅读0次

    二分查找(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 区间内,如果在,我们就取出对应的归属地显示;如果不在,就返回未查找到。

    相关文章

      网友评论

          本文标题:数据结构之二分查找

          本文链接:https://www.haomeiwen.com/subject/rkkjyrtx.html