如何通过图解理解并实现二分查找算法实例？

本文共计3497个文字，预计阅读时间需要14分钟。

前言：当我们需要从一个有序序列中查找一个元素的时候，二分查找是一种非常快速查找算法，也称为折半查找。

二分查找的要求有两个：

1.要查找的序列必须是有序的（即有序或有顺序的）。

2.该序列最好是升序的。

前言

当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法，二分查找又叫折半查找。

 

它对要查找的序列有两个要求，一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以，本文假设是升序排列的），二是该序列必须是顺序存储的。

 

如果一个序列是无序的或者是链表，那么该序列就不能进行二分查找。之所以被查找的序列要满足这样的条件，是由二分查找算法的原理决定的。

 

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

 

二分查找能应用于任何类型的数据，只要能将这些数据按照某种规则进行排序。然而，正因为它依赖于一个有序的集合，这使得它在处理那些频繁插入和删除操作的数据集时不太高效。这是因为，对于插入和操作来说，为了保证查找过程正常进行，必须保证数据集始终有序。相对于查找来说，维护一个有序数据集的代价更高。此外，元素必须存储在连续的空间中。因此，当待搜索的集合是相对静态的数据集时，此时使用二分查找是最好的选择。

算法原理

二分查找算法的原理如下：

• 1、如果待查序列为空，那么就返回-1，并退出算法；这表示查找不到目标元素。