C++ 二分查找

我们将讨论 C++ 编程语言中的二分查找。二分查找是一种通过不断将数组减半，然后从减半后的数组中查找指定元素来从已排序数组中查找给定元素的机制。这个过程一直持续到找到匹配项为止。它只适用于已排序的数据结构。二分查找算法的时间复杂度是 O (log n)。

注意：要在 C++ 中执行二分查找技术，程序员或用户应确保给定数组必须按升序或降序排序。

C++ 中二分查找的算法

以下是执行 C++ 中二分查找的算法

在 C++ 中执行二分查找的步骤

步骤 1：声明变量并按排序顺序（升序或降序）输入数组的所有元素。

步骤 2：将数组元素列表分成两半。

步骤 3：现在将目标元素与数组的中间元素进行比较。如果目标元素的值与中间元素匹配，则返回中间元素的位置并结束查找过程。

步骤 4：如果目标元素小于中间元素，我们将在数组的下半部分查找元素。

步骤 5：如果目标元素大于中间元素，我们需要在数组的后半部分查找元素。

步骤 6：我们将不断重复步骤 4、5 和 6，直到在已排序数组中找到指定的元素。

示例 1：使用二分查找从已排序数组中查找指定数字的程序

让我们编写一个程序，使用 C++ 编程语言中的二分查找从已排序数组中查找指定数字。

输出

Define the size of the array: 
10
Enter the values in sorted array either ascending or descending order:
Arr [0]  = 12
Arr [1]  = 24
Arr [2]  = 36
Arr [3]  = 48
Arr [4]  = 50
Arr [5]  = 54
Arr [6]  = 58
Arr [7]  = 60
Arr [8]  = 72
Arr [9]  = 84
Define a value to be searched from sorted array:
50
Element is found at index 5   

示例 2：使用用户定义函数执行二分查找的程序

输出

Element is found at position 5    

在上面的程序中，我们声明了一个数组 arr[] = {5, 10, 15, 20, 25, 30, 35, 40}；然后我们指定数字 '25'，使用二分查找方法从已排序数组中查找它。因此，我们创建了一个用户定义函数 bin_search()，它查找给定数字并返回语句 "Element is found at position 5"。如果数组中没有定义该数字，则 bin_search() 函数会显示 "Element is not found in the array."

示例 3：使用递归函数查找指定元素的程序

让我们创建一个示例，检查是否在递归函数内部使用二分查找在已排序数组中找到指定元素。

输出

Define the size of an array: 10
Arr [0] = 2
Arr [1] = 4
Arr [2] = 5
Arr [3] = 8
Arr [4] = 12
Arr [5] = 13
Arr [6] = 27
Arr [7] = 36
Arr [8] = 49
Arr [9] = 51

Enter an element to be searched in ascending array: 12
12 is available at position 6.   

在上面的程序中，我们按升序输入了数组的所有元素，然后定义了一个数字作为目标元素 '12'，它使用二分查找方法从已排序数组中查找。因此，我们创建了一个用户定义函数 binary_search()，它从数组中查找定义元素的位置并返回此位置可用的特定元素。如果元素在已排序数组中不可用，则返回 0。