二分查找算法

二分查找算法是一种高效的查找算法，适用于在有序数组中查找目标值。其基本思想是将目标值与数组中间元素进行比较，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。如此反复，直到找到目标值或查找范围为空。

C++ 实现

#include <iostream>
#include <vector>
using namespace std;
// 二分查找函数
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left &lt;= right) {
    int mid = left + (right - left) / 2;
    
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] &lt; target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

return -1;

}
int main() {
int n, q;
cin >> n >> q;
vector&lt;int&gt; nums(n);
for (int i = 0; i &lt; n; i++) {
    cin &gt;&gt; nums[i];
}

for (int i = 0; i &lt; q; i++) {
    int x;
    cin &gt;&gt; x;
    
    int result = binarySearch(nums, x);
    cout &lt;&lt; result &lt;&lt; endl;
}

return 0;

}

应用

二分查找算法在很多领域都有应用，例如：

• 查找字典中的单词
• 查找数据库中的记录
• 在代码中查找特定的函数或变量

总结

二分查找算法是一种高效的查找算法，可以显著提高查找速度。在需要在有序数组中查找目标值时，二分查找算法是一个不错的选择。