大佬教程收集整理的这篇文章主要介绍了二分搜索算法(C++详解版),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
Set first to 0 Set last to the last subscript in the array Set found to false Set position to -1 While found is not true and first is less than or equal to last Set middle to the subscript halfway between first and last If arraY[R_198_11845@iddle] equals the desired value Set found to true Set position to middle Else If arraY[R_198_11845@iddle] is greater than the desired value Set last to middle - 1 Else Set first to middle + 1 End If End While Return position该算法使用 3 个索引变量:first、last 和 middle。first 和 last 变量标记当前正在搜索的数组部分的边界。它们用数组的第一个和最后一个元素的下标进行初始化。middle 则是在 first 和 last 元素之间大约中点位置的元素的下标,该值的计算方法就是釆用 first 和 last 相加求和然后除以 2,结果将被存储在 middle 变量中。
int binarySearch(const int arraY[],int size,int value) { int first = 0,//第一个数组元素 last = size - 1,//最后一个数组元素 middle,//搜索的中点 position = -1; //搜索值的位置 bool found = false; // 标记 while (!found && first <= last) { middle = (first + last) / 2; // 计算中点 if (arraY[R_198_11845@iddle] == value) // 如果在中点发现值 { found = true; position = middle; } else if (array [middle] > value) // 如果值在下半部分 last = middle - 1; else first = middle + 1; //如果值在上半部分 } return position; }下面的程序是一个使用 binarySearch 函数的完整程序。它将搜索一个包含员工 ID 号的数组,以查找特定的值。
//This program performs a binary search on an Integer array whose elements are in ascending order. #include <iostream> using namespace std; //Function prototype int binarySearch(const int [],int,int); const int SIZE = 20; int main() { // Create an array of id numbers sorted in ascending order int idnums[SIZE] = {101,142,147,189,199,207,222,234,289,296,310,319,388,394,417,429,447,521,536,600 }; int empID,// Holds the ID to search for results;//Holds the search results // Get an employee ID to search for cout << "Enter the employee ID you wish to search for: "; cin >> empID; // Search for the ID results = binarySearch(IDnums,SIZE,empID); // If binarySearch returned -1,the ID was not found if (results == -1) cout << "That number does not exist in the array.\n"; else { // Otherwise results contains the subscript of // the specified employee ID in the array cout << "ID " << empID << " was found in element " << results << " of the array.\n"; } return 0; } int binarySearch(const int arraY[],// First array element last = size - 1,// Last array element middle,// Midpoint of search position = -1; // Position of search value bool found = false; // Flag while (!found && first <= last) { middle = (first + last) / 2; // Calculate midpoint if (arraY[R_198_11845@iddle] == value) // If value is found at mid { found = true; position = middle; } else if (arraY[R_198_11845@iddle] > value) // If value is in lower half last = middle - 1; else first = middle +1; // If value is in upper half } return position; }程序输出结果:
Enter the employee ID you wish to search for: 199
ID 199 was found in element 4 of the array.
以上是大佬教程为你收集整理的二分搜索算法(C++详解版)全部内容,希望文章能够帮你解决二分搜索算法(C++详解版)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。