算法——二分查找

曾经终败给现在 2021-11-05 09:54 406阅读 0赞

### 文章目录 ###

*  前言
 *  介绍
 *  特点
 *  基本思想
 *  实现
 *  总结
 *  代码实现

# 前言 #

为了学习面试中常常要考察到的二分查找，在网上搜索了很多篇资料，才大致搞懂了二分查找的原理。现在作出总结，以防日后忘记。

# 介绍 #

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

# 特点 #

*  时间复杂度
    
     *  最好情况：O(1)
     *  平均情况：O( l o g 2 n log\_2n log2n)
     *  最坏情况：O( l o g 2 n log\_2n log2n)
 *  空间复杂度：O(1)
 *  稳定性：稳定
 *  **使用条件**
    
     *  必须采用顺序存储结构
     *  必须按关键字大小有序排列

# 基本思想 #

*  二分查找是一种非常高效的算法，又称之为**折半查找**，顾名思义就是将查找的值和数组的中间值作比较
 *  如果被查找的值小于中间值，就在中间值左侧数组继续查找；如果大于中间值，就在中间值右侧数组中查找；否则中间值就是要找的元素。
 *  二分查找的优缺点：
    
     *  优点：比较次数少，查找速度快，平均性能好；
     *  缺点：要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

# 实现 #

假设存在这样一个数组a\[8\]，数组中存在有8个**按顺序存储**的数：

a[8] = [1,2,3,4,5,6,7,8];

用表格来将这个数组展示出来，表格如下：

**表格①**

首先，取数组的初始索引值（low=0），末尾索引值（high=7），再根据这两个值取中间索引值（mid = （low + high） / 2 = 3），将这三个表示加入到表格中，表格如下：

**表格②**

假设这里想要查找的值是“5”。  
这时比较5与**mid索引**的值（4），因为5>4，所以需要查找以mid为分界线的右半区。此时，low的索引值变为low = mid + 1 = 4，而mid的值转变为mid = （low + high） / 2 = 5，表格如下：

**表格③**

这时比较5与**mid索引**的值（6），因为5<6，所以需要查找以mid为分界线的左半区。此时，high的索引值变为high = mid - 1 = 4，而mid的值转变为mid = （low + high） / 2 = 4，表格如下：

**表格④**

此时，mid的索引对应的值与想要查找的值对应，查找结束

# 总结 #

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

# 代码实现 #

这里仅列出用Java代码实现的版本，其他版本可以参考网上的其他资料

public static int binarySearch(Integer[] srcArray, int des) { 
        //定义初始最小、最大索引
        int start = 0;
        int end = srcArray.length - 1;
        //确保不会出现重复查找，越界
        while (start <= end) { 
            //计算出中间索引值
            int middle = (end + start)>>>1 ;//防止溢出
            if (des == srcArray[middle]) { 
                return middle;
            //判断下限
            } else if (des < srcArray[middle]) { 
                end = middle - 1;
            //判断上限
            } else { 
                start = middle + 1;
            }
        }
        //若没有，则返回-1
        return -1;
    }