C++ Binary Search: Algorithm & Code Example - Efficient Search Technique

{"title":"C++ Binary Search: Algorithm & Code Example - Efficient Search Technique","description":"Learn the fundamental C++ binary search algorithm and its implementation. Discover how to efficiently find a target value in a sorted array with step-by-step instructions and a code example.","keywords":"C++, binary search, algorithm, code, example, sorted array, search technique, efficient search, find target, index","content":"C++中进行二分查找的大框架如下：\n\n1. 确定搜索区间的上界和下界。一般情况下，上界为数组的长度减一，下界为0。\n\n2. 使用一个循环来不断缩小搜索范围，直到找到目标值或者搜索范围为空。\n\n3. 在循环中，计算出搜索范围的中间位置mid，可以使用以下公式计算：mid = (low + high) / 2。\n\n4. 判断中间位置的元素与目标值的关系，如果中间位置的元素等于目标值，则找到了目标值，返回结果；如果中间位置的元素大于目标值，则目标值在左半部分，将搜索范围的上界更新为mid-1；如果中间位置的元素小于目标值，则目标值在右半部分，将搜索范围的下界更新为mid+1。\n\n5. 如果循环结束时仍然没有找到目标值，则返回不存在的结果。\n\n下面是一个具体的示例代码：\n\ncpp\nint binarySearch(vector<int>& nums, int target) {\n int low = 0;\n int high = nums.size() - 1;\n\n while (low <= high) {\n int mid = (low + high) / 2;\n if (nums[mid] == target) {\n return mid;\n } else if (nums[mid] > target) {\n high = mid - 1;\n } else {\n low = mid + 1;\n }\n }\n\n return -1; // 目标值不存在\n}\n\n\n这个示例代码假设输入的nums是一个已经有序的数组，如果数组中存在目标值target，则返回目标值的索引，否则返回-1。"}