二分查找


阅读数: 次   

概述

本文是对上篇博客的后续补充，是的，我们迎来了五月，今天我们来介绍三大算法之一二分查找。

二分查找(Binary Search)算法，也叫折半查找算法。二分查找是一种非常简单易懂的快速查找算法，其思想在生活中随处可见，比如朋友聚会的时候爱玩的一个猜数游戏，我随机写一个 0-100 之间的数字，然后大家依次来猜，猜的过程中大家每猜一次我都会告诉大家猜大了还是猜小了，直到有人猜中为止，猜中的人会有一些惩罚措施。这个过程其实就是二分查找思想的一种体现。

原理

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0

时间复杂度

我们假设数据大小为 n，每次查找完后数据的大小缩减为原来的一半，直到最后数据大小被缩减为 1 此时停止，如果我们用数据来描述其变化的规律那就是：

n， n/2， n/4， n/8， n/16， n/32， …………………..， 1；
可以看出来，这是一个等比数列，当数据大小变为 1 时：其中 k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以， 经过了 k 次区间缩小操作，通过计算 k 的值我们可以得出二分查找的时间复杂度就是 O(logn)

这是一种非常高效的时间复杂度，有时候甚至比 O(1)复杂度更高效 ：

O(1)代表的是一种常量级复杂度并不是说代码只需要执行一次，有时候可能要执行 100 次， 1000 次这种常数级次数的复杂度都可以用O(1)表示，所以，常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高

实现代码

1.有序数列中不存在重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package com.jy.binarySerach;

public class SimpleBinary {
    public static void main(String[] args) {
        int[] array = new int[10];
        array[0] = 6;
        array[1] = 12;
        array[2] = 15;
        array[3] = 19;
        array[4] = 24;
        array[5] = 26;
        array[6] = 29;
        array[7] = 35;
        array[8] = 46;
        array[9] = 67;
        //		int i = cicleBinarySerach(array, 15);
        int i = recursionBinarySearch(array, 15,0,array.length-1);
        System.out.println("找到了目标元素的下标:"+i+"---对应的值为:"+array[i]);
    }
    /**
	 * 递归查找
	 * @param array
	 * @param value
	 * @param low
	 * @param high
	 * @return
	 */
    public static int recursionBinarySearch(int[] array,int value,int low,int high) {
        //终止条件
        if(low>high)return -1;
        int mid = (low+high)/2;
        if(array[mid]==value) {
            return mid;
        }else if(array[mid]<value) {
            return recursionBinarySearch(array, value, mid+1, high);
        }else {
            return recursionBinarySearch(array, value, low, mid-1);
        }
    }

    /**
	 * 使用非递归的形式查找
	 * @param array 待查找的有序数组
	 * @param value 要查找的数值
	 * @return
	 */
    public static int cicleBinarySerach(int[] array,int value) {
        int low = 0;
        int high = array.length-1;
        while(low<=high) {
            int mid = (low+high)/2;//中间元素下标
            if(array[mid]==value) {
                return mid;
            }else if(array[mid]>value) {
                high = mid-1;
            }else {
                low = mid+1;
            }
        }
        //如果至此还未找到则返回-1 代表未找到匹配的元素
        return -1;
    }

}

2.有序数列中存在重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package com.jy.binarySerach;

public class NeedsBinary {
    public static void main(String[] args) {
        //准备一个 int 数组 6， 12， 15， 19， 24， 26， 29， 29， 29， 67
        int[] array = new int[10];
        array[0] = 6;
        array[1] = 12;
        array[2] = 15;
        array[3] = 19;
        array[4] = 24;
        array[5] = 26;
        array[6] = 29;
        array[7] = 29;
        array[8] = 29;
        array[9] = 67;
        //		int i = binarySearchFirst(array, 29);
        //		int i = binarySearchLast(array, 29);
        //		int i = binarySearchFirstBigger(array, 28);
        int i = binarySearchLastSmaller(array, 30);
        System.out.println("找到了目标元素的下标:"+i+"---对应的值为:"+array[i]);
    }
    /**
	 * 查找数据序列中第一个等于给定值的元素的下标
	 * @param array
	 * @param value
	 * @return
	 */
    public static int binarySearchFirst(int[] array,int value) {
        int low = 0;
        int high = array.length-1;
        while(low<=high) {
            int mid = (low+high)/2;//中间元素下标
            if(array[mid]==value) {
                //由于数据序列是有序的,因此我们判断是否指向第一个元素或者向前一位查看一下是否也等于该值,如果相等则继续二分查找,否则直接返回 mid
                if(mid==0||array[mid-1]!=value) {
                    return mid;
                }else {
                    high = mid-1;
                }	
            }else if(array[mid]>value) {
                high = mid-1;
            }else {
                low = mid+1;
            }
        }
        return -1;
    }

    /**
	 * 查找数据序列中最后一个等于给定值的元素的下标
	 * @param array
	 * @param value
	 * @return
	 */
    public static int binarySearchLast(int[] array,int value) {
        int low = 0;
        int high = array.length-1;
        while(low<=high) {
            int mid = (low+high)/2;//中间元素下标
            if(array[mid]==value) {
                if(mid==array.length-1||array[mid+1]!=value) {
                    return mid;
                }else {
                    low = mid+1;
                }	
            }else if(array[mid]>value) {
                high = mid-1;
            }else {
                low = mid+1;
            }
        }
        return -1;
    }

    /**
	 * 从数据序列中查找第一个大于等于给定值的元素
	 * @param array
	 * @param value
	 * @return
	 */
    public static int binarySearchFirstBigger(int[] array,int value) {
        int low = 0;
        int high = array.length-1;
        while(low<=high) {
            int mid = (low+high)/2;//中间元素下标
            if(array[mid]>=value) {
                if(mid==0||array[mid-1]<value) {
                    return mid;
                }else {
                    high = mid-1;
                }	
            }else {
                low = mid+1;
            }
        }
        return -1;
    }
    /**
	 * 从数据序列中查找出最后一个值小于等于给定值的元素
	 * @param array
	 * @param value
	 * @return
	 */
    public static int binarySearchLastSmaller(int[] array,int value) {
        int low = 0;
        int high = array.length-1;
        while(low<=high) {
            int mid = (low+high)/2;//中间元素下标
            if(array[mid]<=value) {
                if(mid==array.length-1||array[mid+1]>value) {
                    return mid;
                }else {
                    low = mid+1;
                }	
            }else {
                high = mid-1;
            }
        }
        return -1;
    }
}

二分查找的使用条件及场景

1.待查找的数据序列必须有序

二分查找对这一要求比较苛刻， 待查找的数据序列必须是有序的，假如数据无序，那我们要先排序，然后二分查找，通过前面排序算法的学习我们知道，如果我们针对的是一组固定的静态数据，也就说该数据序列不会进行插入和删除操作，那我们完全可以先排序然后二分查找，这样子一次排序多次查找；但是如果数据序列本身不是固定的静态的，可能涉及数据序列的插入和删除操作，那我们每次查找前都需要进行排序然后才能查找，这样子成本非常的高。

2.数据的存储依赖数组

待查找的数据序列需要使用数组进存储，也就是说依赖顺序存储结构。

二分查找，算法需要根据下标，low,high,mid 来访问数据序列中的元素，数组按照下标访问元素的复杂度是O(1)，而链表访问元素的时间复杂度是 O(n)，因此如果使用链表来存储数据二分查找的时间复杂度就会变得很高。

3.数据量太小或太大都不适合用二分查找

数据量很小的情况下，没有必要使用二分查找，使用循环遍历就够了，因为只有在数据量比较大的情况下二分查找才能体出优势，不过在某些情况下即使数据量很小也建议大家使用二分查找，比如数据序列中的数据都是一些长度非常长的字符串，这些长度非常长的字符串比较起来也会非常的耗时，所以我们要尽可能的减少比较的次数，这样反倒有助于提高性能。

为什么数据量太大的情况下也不建议使用二分查找呢？因为我们前面刚讲到二分查找底层需要依赖数组存储待查找的数据序列，而数组的特点是需要连续的内存空间，比如现在有 1G 的订单数据，如果用数组来存储就需要 1G 的连续内存，即便有 2G 的剩余内存空间，如果这 2G 的内存空间不连续那也无法申请到 1G 大小的数组空间，所以我们说数据量太大也不适合用二分查找。

结语

“请问有没有五月一号到期的凤梨罐头？”——王家卫《重庆森林》

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家