数据结构中的线性搜索和二分搜索是什么？

线性搜索和二分搜索都是用于搜索元素的查找方法。我们将这两种方法都应用于一个数组和一个键值；我们需要做的就是在此数组中搜索该键。如果我们找到它，我们将返回与该键值对应的索引。如果我们未能在此数组中找到该键，那么我们将打印一条消息，告知该值未找到。

• 在进行线性搜索时，我们不需要对数组进行排序，也不需要按升序或降序排列。
• 在进行二分搜索时，在我们应用二分搜索对数组进行操作之前，我们首先需要对数组进行排序，无论是按升序还是降序。
• 在线性搜索中，我们将线性地遍历数组，并逐个地、顺序地将每个数组元素与键进行比较。
• 在二分搜索中，我们将应用分治法；首先，我们将找到中间元素，然后将数组分成两部分。一次，我们将只处理其中一部分来获得所需的结果。
• 二分搜索比线性搜索方法更有效。
• 如果给定的数组已排序，我们应该优先选择二分搜索方法而不是线性搜索。
• 但是，如果给定的数组未排序，那么二分搜索方法在与线性搜索相比时不是一种有效的方法。

让我们更详细地讨论线性搜索和二分搜索。

数据结构中的线性搜索

目标：线性搜索用于搜索数组中存在的任何元素。在线性搜索中，我们不需要排序的数组。可以使用任何随机数组来查找元素。我们提供一个数组和一个键值；键值就是需要在此给定数组中搜索的值。如果在数组中成功找到该数组，我们需要返回该值的相应索引。返回索引的原因是我们返回该键值或元素在数组中存在的位置。如果该值在数组中未找到，那么我们需要返回一个简单的语句，即该值不在数组中。

实现线性搜索以搜索元素的算法-

步骤 1 - 从用户那里获取一个包含 'n' 个元素的数组；元素是指主函数中的非负整数。还要从用户那里获取键值，以便相应地生成结果。

步骤 2 - 调用线性搜索函数以从数组中查找该键值的相应索引。将原始数组、元素数量以及键值、数组和数组大小作为参数传递到该函数中。

步骤 3 - 我们可以使用两种方法来实现线性搜索函数；一种是使用简单的循环迭代，另一种是递归方法。

步骤 4 - 使用迭代方法，我们将使用循环，具体取决于程序员他们将使用哪种类型的循环，无论是 for 循环、while 循环还是 do-while 循环。

步骤 5 - 实现循环的基本标准是，从数组的 0 到大小 - 1 运行循环；在循环体内，我们将检查条件，即键的值是否与索引 i 匹配，如果匹配，我们将中断循环并返回 i 的值，它表示数组的索引，否则我们将 i 的值加 1 并重复循环直到找到键或数组结束。

步骤 6 - 如果我们使用递归方法，我们将把基本条件写在函数中，例如，如果最后一个索引处存在的值与键值匹配，我们将返回索引。否则，我们将减小数组的大小并再次递归调用相同的线性搜索函数。

步骤 7 - 如果该值与数组元素不匹配，我们将返回 -1。

步骤 8 - -1 将在主函数中返回，然后在主函数中，我们将检查条件，例如，如果返回值等于 -1，那么我们将打印消息，告知该键在数组中未找到。如果值不等于 -1，那么我们将简单地打印消息，告知该键在特定索引 i 处找到。

步骤 9 - 最后，我们将在屏幕上获得期望的输出。

使用迭代方法在 C 编程语言中实现线性搜索

上述程序的输出

Enter the size of an array: 10
Enter Array
 12
13
15
8
7
9
6
11
10
4
 Enter the value to search: 7
 Value present at index: 4

使用迭代方法在 C++ 编程语言中实现线性搜索

上述程序的输出

Enter the size of an array: 10
Enter Array
 12
13
15
8
7
9
6
11
10
4
 Enter the value to search: 7
 Value present at index: 4

使用迭代方法在 Java 编程语言中实现线性搜索

上述程序的输出

Enter the size of an array: 10
Enter Array
 12
13
15
8
7
9
6
11
10
4
 Enter the value to search: 7
 Value present at index: 4

使用递归方法在 C 编程语言中实现线性搜索

上述程序的输出

Enter the size of an array: 10
Enter Array
 12
13
15
8
7
9
6
11
10
4
 Enter the value to search: 7
 Value present at index: 4

使用递归方法在 C++ 编程语言中实现线性搜索

上述程序的输出

Enter the size of an array: 10
Enter Array
 12
13
15
8
7
9
6
11
10
4
 Enter the value to search: 7
 Value present at index: 4

使用递归方法在 Java 编程语言中实现线性搜索

上述程序的输出

Enter the size of an array: 10
Enter Array
 12
13
15
8
7
9
6
11
10
4
 Enter the value to search: 7
 Value present at index: 4

数据结构中的二分搜索

目标：二分搜索用于搜索数组中存在的任何元素。在二分搜索中，我们必须有一个排序的数组，不能使用任何随机数组来从中查找元素。我们提供一个数组和一个键值；键值就是需要在此给定数组中搜索的值。如果在数组中成功找到该数组，我们需要返回该值的相应索引。返回索引的原因是我们返回该键值或元素在数组中存在的位置。如果该值在数组中未找到，那么我们需要返回一个简单的语句，即该值不在数组中。如果用户提供的数组未排序，那么我们首先需要对数组进行排序，然后再对其应用搜索过程。

实现二分搜索以搜索元素的算法-

步骤 1 - 从用户那里获取一个包含 'n' 个元素的数组；元素是指主函数中的非负整数。还要从用户那里获取键值，以便相应地生成结果。

步骤 2 - 调用二分搜索函数以从数组中查找该键值的相应索引。将原始数组、已排序数组的第一个索引、已排序数组的最后一个索引以及键值和数组大小作为参数传递到该函数中。

步骤 3 - 我们可以使用两种方法来实现二分搜索函数；一种是使用简单的循环迭代，另一种是递归方法。

步骤 4 - 使用迭代方法，我们将使用循环，具体取决于程序员他们将使用哪种类型的循环，无论是 for 循环、while 循环还是 do-while 循环。

步骤 5 - 如果我们使用递归方法，那么我们将不使用循环，而是简单地在函数中编写基本条件，例如，如果最后一个索引处存在的值与键值匹配，那么我们将返回索引，否则我们将减小数组的大小并再次递归调用相同的线性搜索函数。

步骤 6 - 实现循环的基本标准是，从数组的 0 到大小 - 1 运行循环；在循环体内，我们将检查条件，即键的值是否与中间元素匹配，如果匹配，我们将中断循环并返回中间值，它表示数组的索引，否则我们将简单地将 i 的值加 1 并重复循环直到找到键或数组结束。

步骤 7 - 如果中间元素大于键值，那么我们将划分数组并调用从索引 0 开始到中间索引 - 1 结束的数组，然后其余工作将在另一半完成，并且相同过程将对相同元素重复。

步骤 8 - 如果键值超过中间元素，我们将再次划分数组并调用从中间索引 + 1 到 n 开始的数组。在所有上述情况下，如果任何情况将键值与中间值匹配，我们将返回中间值，它表示键值的索引。

步骤 9 - 如果该值与数组元素不匹配，我们将返回 -1。

步骤 10 - -1 将在主函数中返回，然后在主函数中，我们将检查条件，例如，如果返回值等于 -1，那么我们将打印消息，告知该键在数组中未找到。如果值不等于 -1，那么我们将简单地打印消息，告知该键在特定索引 i 处找到。

步骤 11 - 最后，我们将在屏幕上获得期望的输出。

使用迭代方法在 C 编程语言中实现二分搜索

上述程序的输出

Enter the size of an array: 10
Enter Sorted Array
 12
13
15
18
20
22
26
30
40
44
 Enter the value to search: 20
 Value present at index: 4

使用迭代方法在 C++ 编程语言中实现二分搜索

上述程序的输出

Enter the size of an array: 10
Enter Sorted Array
 12
13
15
18
20
22
26
30
40
44
 Enter the value to search: 20
 Value present at index: 4

使用迭代方法在 Java 编程语言中实现二分搜索

上述程序的输出

Enter the size of an array: 10
Enter Sorted Array
 12
13
15
18
20
22
26
30
40
44
 Enter the value to search: 20
 Value present at index: 4

使用递归方法在 C 编程语言中实现二分搜索

上述程序的输出

Enter the size of an array: 10
Enter Sorted Array
 12
13
15
18
20
22
26
30
40
44
 Enter the value to search: 20
 Value present at index: 4

使用递归方法在 C++ 编程语言中实现二分搜索

上述程序的输出

Enter the size of an array: 10
Enter Sorted Array
 12
13
15
18
20
22
26
30
40
44
 Enter the value to search: 20
 Value present at index: 4

使用递归方法在 Java 编程语言中实现二分搜索

上述程序的输出

Enter the size of an array: 10
Enter Sorted Array
 12
13
15
18
20
22
26
30
40
44
 Enter the value to search: 20
 Value present at index: 4