极客笔记C++ 二分查找
我们将讨论C++编程语言中的二分查找。二分查找是一种机制，它通过不断将数组分成两半，并从其中一半中查找指定元素来找到给定元素。这个过程一直进行，直到找到匹配项。它仅适用于已排序的数据结构。二分查找算法的时间复杂度为O(log n)。
注意：在C++中执行二分搜索技术时，程序员或用户应确保给定的数组必须按升序或降序排序。
在C++中执行二分搜索的算法
以下是在C++中执行二分搜索的算法。
beg = 0;
end = size - 1;
while ( beg <= end)
{
// calculate mid value
mid = (beg + end) / 2;
/* if the specified element is found at mid index, terminate the process and return the index. */
// Check middle element is equal to the defined element.
If (aarr[mid] == num)
{
return mid + 1;
}
else if (arr[mid] > num)
{
End = mid - 1;
}
Else if (arr [mid] < num)
{
Beg = mid + 1;
}
}
// If the element does not exist in the array, return -1.
Return -1;
在C++中执行二分搜索的步骤
步骤1: 声明变量并按照排序顺序（升序或降序）输入数组的所有元素。
步骤2: 将数组元素的列表分成两半。
步骤3: 现在将目标元素与数组的中间元素进行比较。如果目标元素的值与中间元素匹配，则返回中间元素的位置并结束搜索过程。
步骤4: 如果目标元素小于中间元素，则在数组的较低半部分搜索元素。
步骤5: 如果目标元素大于中间元素，则需要在数组的较高半部分搜索元素。
步骤6: 我们将重复执行步骤4、5和6，直到在排序后的数组中找到指定的元素。
示例1：使用二分搜索从排序数组中找到指定的数字的程序
让我们使用C++编程语言编写一个程序，在排序数组中使用二分搜索找到指定的数字。
#include <iostream>
#include <conio.h>
using namespace std;
int main ()
{
// declaration of the variables and array
int arr[100], st, mid, end, i, num, tgt;
cout << " Define the size of the array: " << endl;
cin >> num; // get size
// enter only sorted array
cout << " Enter the values in sorted array either ascending or descending order: " << endl;
// use for loop to iterate values
for (i = 0; i < num; i++)
{
cout << " arr [" << i << "] = ";
cin >> arr[i];
}
// initialize the starting and ending variable's values
st = 0;
end = num - 1; // size of array (num) - 1
// define the item or value to be search
cout << " Define a value to be searched from sorted array: " << endl;
cin >> tgt;
// use while loop to check 'st', should be less than equal to 'end'.
while ( st <= end)
{
// get middle value by splitting into half
mid = ( st + end ) / 2;
/* if we get the target value at mid index, print the position and exit from the program. */
if (arr[mid] == tgt)
{
cout << " Element is found at index " << (mid + 1);
exit (0); // use for exit program the program
}
// check the value of target element is greater than the mid element' value
else if ( tgt > arr[mid])
{
st = mid + 1; // set the new value for st variable
}
// check the value of target element is less than the mid element' value
else if ( tgt < arr[mid])
{
end = mid - 1; // set the new value for end variable
}
}
cout << " Number is not found. " << endl;
return 0;
}
输出
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: 使用用户定义的函数执行二分搜索的程序
/* program to find the specified element from the sorted array using the binary search in C++. */
#include <iostream>
using namespace std;
/* create user-defined function and pass different parameters:
arr[] - it represents the sorted array;
num variable represents the size of an array;
tgt variable represents the target or specified variable to be searched in the sorted array. */
int bin_search (int arr[], int num, int tgt)
{
int beg = 0, end = num - 1;
// use loop to check all sorted elements
while (beg <= end)
{
/* get the mid value of sorted array and then compares with target element. */
int mid = (beg + end) /2;
if (tgt == arr[mid])
{
return mid; // when mid is equal to tgt value
}
// check tgt is less than mid value, discard left element
else if (tgt < arr[mid])
{
end = mid - 1;
}
// if the target is greater than the mid value, discard all elements
else {
beg = mid + 1;
}
}
// return -1 when target is not exists in the array
return -1;
}
int main ()
{
// declaration of the arrays
int arr[] = { 5, 10, 15, 20, 25, 30, 37, 40};
int tgt = 25; // specified the target element
int num = sizeof (arr) / sizeof (arr[0]);
// declare pos variable to get the position of the specified element
int pos = bin_search (arr, num, tgt);
if (pos != 1)
{
cout << " Element is found at position " << (pos + 1)<< endl;
}
else
{
cout << " Element is not found in the array" << endl;
}
return 0;
}
输出
Element is found at position 5
在上面的程序中，我们声明了一个数组arr[] = {5, 10, 15, 20, 25, 30, 35, 40}，然后我们指定了要从已排序的数组中搜索的数字’25’，使用二分搜索方法。因此，我们创建了一个自定义函数bin_search()，它搜索给定的数字并返回语句”元素位于位置5″。如果该数字在数组中没有定义，bin_search()函数显示”数组中未找到元素”。
示例3：使用递归函数查找指定元素的程序
让我们创建一个示例，通过递归函数在已排序的数组中使用二分搜索来检查指定的元素是否存在。
/* find the specified number using the binary search technique inside the recursion method. */
#include <iostream>
using namespace std;
// define a function
int binary_search (int [], int, int, int);
int main ()
{
// declaration of the variables
int i, arr[100], tgt, num, ind, st, end;
cout << " Define the size of an array: ";
cin >> num;
cout << " Enter " << num << " elements in ascending order: " << endl;
// use for loop to ieterate the number
for ( i = 0; i < num; i++)
{
cout << " arr [" << i << "] = ";
cin >> arr[i];
}
// define the element to be search
cout << " \n Enter an element to be searched in ascending array: ";
cin >> tgt;
// ind define the index number
ind = binary_search (arr, 0, num - 1, tgt);
// check for existemce of the specified element
if (ind == 0)
cout << tgt << " is not available in the array-list";
else
cout << tgt << " is available at position " << ind << endl;
return 0;
}
// function defnition
int binary_search (int arr[], int st, int end, int tgt)
{
int mid;
// check st is greater than end
if (st > end)
{
return 0;
}
mid = (st + end) / 2; // get middle value of the sorted array
// check middle value is equal to target number
if (arr[mid] == tgt)
{
return (mid + 1);
}
// check mid is greater than target number
else if (arr[mid] > tgt)
{
binary_search (arr, st, mid - 1, tgt);
}
// check mid is less than target number
else if (arr [mid] < tgt)
{
binary_search (arr, mid + 1, end, tgt);
}
}
输出
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。