二分查找有几种写法？它们的区别是什么?

来源：千锋教育

发布人：xqq

时间： 2023-10-16 07:57:38

一、二分查找有几种写法

二分查找是一种常见的查找算法，它适用于已排序的数组或列表中查找指定元素的位置。在实际应用中，二分查找有多种实现方式，以下是比较四种常见的写法：

1、递归写法

递归写法是一种常见的实现方式，它将查找过程递归地分成左右两个部分，并不断缩小查找范围，直到找到目标元素或者查找范围为空。递归写法的实现代码较为简单，但是需要注意递归终止条件和递归过程中参数的传递方式。

2、非递归写法

非递归写法使用循环来实现查找过程，它通过不断缩小查找范围并更新查找的区间来进行查找，直到找到目标元素或者查找范围为空。非递归写法的实现代码较为复杂，但是效率较高，不会出现栈溢出等问题。

3、左闭右闭写法

左闭右闭写法是一种常见的实现方式，它将查找区间定义为左闭右闭区间，即包含左右两端点。这种写法的优点是实现简单，易于理解和使用。

4、左闭右开写法

左闭右开写法将查找区间定义为左闭右开区间，即包含左端点但不包含右端点。这种写法的优点是实现简单，查找区间更为直观，但是需要注意边界条件的处理。

二、二分查找写法之间的区别

以上四种实现方式之间的区别主要体现在以下几个方面：

1、实现方式不同

递归写法和非递归写法的实现方式不同，递归写法使用递归来实现查找过程，非递归写法使用循环来实现查找过程。

2、实现复杂度不同

递归写法的实现代码较为简单，但是需要注意递归终止条件和递归过程中参数的传递方式。非递归写法的实现代码较为复杂，但是效率较高，不会出现栈溢出等问题。

3、区间定义不同

左闭右闭写法和左闭右开写法的区间定义不同，左闭右闭区间包含左右两端点，左闭右开区间包含左端点但不包含右端点。

4、边界处理不同

左闭右闭写法和左闭右开写法的边界处理不同，左闭右闭写法的边界处理比较简单，但是在处理边界时需要注意左右端点的顺序。左闭右开写法的边界处理比较复杂，需要特别注意右端点的边界条件。

在实际应用中，应该根据具体需求和场景选择合适的实现方式。如果数据量较小，递归写法和左闭右闭写法是比较合适的选择；如果数据量较大，非递归写法和左闭右开写法效率更高。同时，不同实现方式之间也可以相互结合，比如可以使用非递归写法和左闭右闭写法结合，以兼顾效率和实现简单性。

延伸阅读1：二分查找的查找长度怎么算

二分查找的查找长度指的是二分查找算法在查找过程中，需要查找的元素个数。一般来说，我们可以通过查找区间的长度来计算二分查找的查找长度。在二分查找的过程中，每次都将查找区间分为两个部分，如果目标元素在左边的区间，则继续在左边的区间进行查找，否则在右边的区间进行查找，以此类推。因此，每次查找后，查找区间的长度都会缩小为原来的一半。

假设初始的查找区间长度为n，则名列前茅次查找后，查找区间的长度缩小为n/2；第二次查找后，查找区间的长度缩小为n/4；第三次查找后，查找区间的长度缩小为n/8，以此类推。因此，可以通过不断将查找区间长度除以2，来计算二分查找的查找长度。

具体而言，如果二分查找的查找区间长度为n，则二分查找的查找长度为log₂n。这是因为，每次查找后，查找区间的长度都会缩小为原来的一半，因此查找次数非常多为log₂n次。

需要注意的是，在实际应用中，二分查找的查找长度可能会受到多种因素的影响，比如查找元素的位置、查找区间的大小、算法的实现方式等等，因此需要根据具体情况进行分析和计算。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。