当前位置：首页 > news >正文

数据结构与算法分析：你真的理解查找算法吗——二分查找（代码详解）

news 2024/10/28 6:08:22

一、算法描述

二分查找在预先排好序的集合上表现出了比顾序查找更好的性能。二分查找每次将有序集合折半直到找到待查找元素,或者发现待查找元素不在当前的集合中。
假设你有一本纽约电话簿,并且需要找到“David Mamet”的电话。如果你使用顺序查找的话,你也许需要花费下午的大部分时间来寻找他的电话号码,或者更坏的是,在知道他的号码是否已经列出之前,你不得不检查电话簿中的每一个条目。很明显的,这个方法没有利用电话簿上名字有序这个特性。所以,你可以翻到电话簿的中页看看“David Mamet”,是否在那页上。如果“David Mamet”这个条目在那一页,那么就到此为止。如果不在,并且“Mamet”在字典序上比这一页上任何一个姓都要靠前,那么你需要在电话簿的前半部去寻找,否则的话,你就需要在电话簿的后半部寻找,这个过程是一种“分治”的策略,能够快速地定位想要找的目标。注意,如果你翻到某一页,这一页上"Mamet"应该出现但是没有出现,那么你知道不用再去查找任何一页,因为Mamet的电话不在这本电话薄上。
二分查找的输入是一个素引集合A。每一个元素A[可有一个键值k,能够用来区分元素。这些健值是有序的,意思是,给定两个键值 $k_{i}$ 和 $k_{j}$ ,要么 $k_{i}<k_{j}$ ,要么 $k_{i}=k_{j}$ ,或者 $k_{i}>k_{j}$ ,我们构造了一个数据结构来保存这些元素(或者这些元素的指针)和维护键值的有序,我们也必须能够将这个数据结构分成数个子集进行查找,这样我们就使用了“分治法”来解决这个问题,二分查找的输出是真或者假。

二、复杂度分析

在这里插入图片描述
二分查找实现稍稍有点复杂但是却获得了巨大的性能提升。当集合并不是存储在简单的内存中数据结构(例如数组)中时会增加实现的复杂性。基于元素的自然序,必须有能够集合中直接在存取元素A(Osi<n)的方式,并且在Comparable接口中实现。较大的集合也许需要存储在二级存储器中,例如在磁盘上以文件的形式。在这种情况下,第个元素能够根据其在文件中的偏移量来存取。如果使用二级存储器,查找一个元素所需要的时间就主要是存取二级存储器所需要的开销,其他和二分查找相关的解决方案也适用。参考"算法优化”一节,其中对这些问题进行了处理。
二分查找每次执行循环时都会大约将问题折半进行处理。将大小为的集合折半的最大次数为log(n),如果用是2的幕,否则的话,就是log(n)。如果我们仅仅使用一个操作来决定两个元素是相等,小于或者大于(这个决定也许是有Conparable接口来做出的),那么仅仅需要log(n)次比较操作,这个算法的性能是O(logn)的。我们执行了100次实验,每次实验在集合中执行524288次查找,这个集合是存储在内存中的,大小为n(n的范围是从4096~524288),目标存在于这个集合中的概率是P(在1.0、0.5和0.0处采样),下表列出的是在拖弃最好和最坏的实验结果后,剩余98次实的
的平均结果。
在这里插入图片描述

设计这些实验的目的是确保在p=1.0时,集合中的所有元素都能够等概率地被查找到,如果不是这样的话,那么这个结果将是不可霧的,对于顺序查找和二分查找来说,输入时一个有序的整数数组,整数的范围在[0.r)。为了产生524288个目标元素,并且这些元素都在这个集合中(pal),我们循环地产生几元素524288/n次。下表列出了在本地磁盘上执行524288次查找的时间。目标元素要么总是存在于集合中(例如p=1.0)或者从不存在(例如,我们在集合[0.n)中查找-1),数据是一个简单的文件,文件存储的是按升序排列的整数,每个整数是4个字节,磁盘存储的优劣务是非常明显的。因为表5-3的结果相比表5-2的结果要慢近200倍。当,加倍时,你将会注意到查找只是增加了固定的时间,这种特性非常明显地表明了二分查找是O(logn)算法。
在这里插入图片描述

三、适用情况

无论查找一个数字集合或者是一个字典序的名字列表,这个方法都能够很好地处理,我们能够看到在最坏时间下需要对数次数的检查。
元素的键值必须是全序的,使得你能够知道一个元素是“大于或者等于”另外一个元素。二分查找能够支持不同种类的数据结构。如果集合是静态的,那么元素能够被放人一个数组中。这样能够更方便快捷地追历集合。但是,如果你需要从集合中添加成者移除元素,这个方法就变得非常笨抽。你可以使用很多数据结构,最著名的一个是二又树,将在“算法优化”中讨论。

四、算法实现

// 二分查找函数，返回目标值的索引，如果未找到则返回-1  
int binarySearch(int arr[], int n, int target) 
{int left = 0;int right = n - 1;while (left <= right){int mid = left + (right - left) / 2; // 防止(left + right)可能导致的溢出  // 检查中间元素是否是目标值  if (arr[mid] == target){return mid; // 找到目标值，返回索引  }// 如果目标值大于中间元素，则忽略左半部分  if (arr[mid] < target) {left = mid + 1;}else { // 如果目标值小于中间元素，则忽略右半部分  right = mid - 1;}}// 如果未找到目标值，则返回-1  return -1;
}int main()
{int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };int n = sizeof(arr) / sizeof(arr[0]);int target = 7;// 调用二分查找函数  int result = binarySearch(arr, n, target);if (result != -1) {printf("目标值 %d 在数组中的索引为 %d\n", target, result);}else {printf("目标值 %d 未在数组中找到\n", target);}return 0;
}

五、算法优化

二分查找有两个主要的变种。第一个和处理动态数据有关,在允许高效地插入或者删除时也需要维护一个可以接受的查找性能,如果集合是以数组的形式存储的话,因为每一个数组的条目都是一个有效的元素,所以插入和删除将会比较低效。因此,插人操作将会扩展这个数组(从逻辑上或者物理上)并且平均需要移动一半的元素。删除需要缩短
数据并且也需要移动一半的元素。任何一个都是不可接受的。
如果集合能够存储在内存中,那么一个好的方法是使用基于散列,并且使用冲突链的查找。见后文“基于散列的查找”,这个查找描述了查找动态数据的方法。一个替代的方法是在内存中构造一个二叉查找树。如果插入和删除操作是随机的,那么这个替代的方法实现起来非常简单,并且树不会偏置。但是,经验告诉我们这种情况很少发生,所
以需要使用查找树的一个更复杂类型——平衡二叉树(Cormen等,2001)。
第二种变种处理的数据是动态的,并且由于过大不能存放在内存中。当这种情况发生时,查找时间就取决于二级存储器的输入输出操作所花费的时间。一个更有效的解决方法是使用叫做日树的元树。这是一个多级树,并且在二级存储器上有较好的性能表现。在http://www.bluerwhite.org/btree上你能找到B树的教程,还包含一些例子。