线性搜索和二进制搜索之间的区别

内容

比较表
线性搜索的定义
二进制搜索的定义
结论

线性搜索和二进制搜索是用于数组的两种方法搜寻要素。搜索是在以任何顺序或随机存储的元素列表中查找元素的过程。

线性搜索和二进制搜索之间的主要区别在于，二进制搜索花费较少的时间从排序的元素列表中搜索元素。因此可以推断二元搜索方法的效率要高于线性搜索。

两者之间的另一个区别是二进制搜索存在先决条件，即元素必须是 已排序 而在线性搜索中没有这样的先决条件。尽管两种搜索方法都使用不同的技术，但下面将对此进行讨论。

比较表
定义
关键差异
结论

比较表


比较依据	线性搜索	二进制搜索
时间复杂度	上）	O（对数 `₂` N）
最佳案例时间	第一元素O（1）	中心元素O（1）
数组的先决条件	不需要	数组必须按排序顺序
N个元素的最坏情况	需要N个比较	只需登录即可得出结论`₂`N个比较
可以实施	数组和链接列表	无法直接在链表上实施
插入操作	轻松插入列表的末尾	需要处理以在适当位置插入以维护排序列表。
算法类型	本质上是迭代的	在自然界中分而治之
有用性	易于使用，不需要任何有序元素。	无论如何，棘手的算法和元素应按顺序组织。
代码行	减	更多

线性搜索的定义

在线性搜索中，以逻辑顺序一个接一个地检索数组的每个元素，并检查是否为所需元素。如果访问了所有元素，但未找到所需的元素，则搜索将失败。在最坏的情况下，我们可能必须扫描平均大小的数目来扫描数组大小的一半（n / 2）。

因此，线性搜索可以定义为依次遍历数组以定位给定项目的技术。下面给出的程序说明了使用search搜索数组元素的过程。

效率线性搜索

在搜索表中的记录中进行搜索所花费的时间或比较次数决定了该技术的效率。如果所需记录出现在搜索表的第一位置，则仅进行一个比较。当所需的记录是最后一个记录时，则必须进行n次比较。如果记录要出现在搜索表中的某处，则平均而言，比较次数将为（n + 1/2）。此技术的最坏情况效率是O（n）表示执行顺序。

C程序 使用线性搜索技术搜索元素。

＃包括＃包括 void main（）{int a，n，i，item，loc = -1; clrscr（）; f（“ n输入元素数量：”）; scanf（“％d”，＆n）; f（“输入数字： n”）; for（i = 0; i <= n-1; i ++）{scanf（“％d”，＆a）; } f（“ n输入要搜索的号码：”）; scanf（“％d”，＆item）; for（i = 0; i <= n-1; i ++）{if（item == a）{loc = i;打破; }} if（loc> = 0）{f（“ n％d在位置％d中找到：”，item，loc + 1）; } else {f（“ n项目不存在”）; } getch（）; }

二进制搜索的定义

二进制搜索是一种非常有效的算法。在最小可能的比较中，这种搜索技术在搜索给定项目时消耗的时间更少。要进行二进制搜索，首先，我们必须对数组元素进行排序。

该技术背后的逻辑如下：

首先，找到数组的中间元素。
将数组的中间元素与要搜索的元素进行比较。

可能出现三种情况：

如果该元素是必需元素，则搜索成功。
当元素小于所需项目时，则仅搜索数组的前半部分。
如果它大于所需的元素，则在数组的后半部分搜索。

重复相同的步骤，直到在搜索区域中找到一个元素或将其用尽。在这种算法中，每次搜索区域都在减少。因此，比较次数最多为log（N + 1）。结果，与线性搜索相比，它是一种有效的算法，但是在进行二进制搜索之前必须对数组进行排序。

C程序 用二进制搜索技术查找元素。

＃包括 void main（）{int i，beg，end，middle，n，search，array; f（“输入元素数 n”）; scanf（“％d”，＆n）; f（“输入％d个数字 n”，n）;对于（i = 0; i <n; i ++）scanf（“％d”，＆array）; f（“输入要搜索的号码 n”）; scanf（“％d”，＆search）; beg = 0; end = n-1;中=（beg + end）/ 2; while（beg <= end）{if（array <search）beg = middle + 1;否则，如果（数组==搜索）{f（“搜索成功。 n％d在位置％d处找到。 n”，搜索，中间+1）；打破; } else end = middle-1;中间=（乞求+结束）/ 2; }如果（beg> end）f（“搜索不成功！列表中没有％d。 n”，搜索）; getch（）; }

线性搜索本质上是迭代的，并使用顺序方法。另一方面，二进制搜索实现了分而治之的方法。
线性搜索的时间复杂度为O（N），而二进制搜索的时间复杂度为O（log₂N）。
线性搜索的最佳情况时间是针对第一个元素，即O（1）。与之相反，在二进制搜索中，它用于中间元素，即O（1）。
在线性搜索中，搜索元素的最坏情况是N个比较。相反，是日志₂用于二进制搜索的N个比较数。
线性搜索可以在数组以及链接列表中实现，而二进制搜索不能直接在链接列表中实现。
众所周知，二进制搜索需要排序数组，这是其原因，它需要进行处理以在适当位置插入以维护排序列表。相反，线性搜索不需要排序的元素，因此可以轻松地将元素插入列表的末尾。
线性搜索易于使用，并且不需要任何有序元素。另一方面，二进制搜索算法很棘手，元素必须按顺序排列。