浙江大学ptaMOOC二分查找完整代码

下面是一个简单的二分查找的完整代码实现，该代码实现了在有序数组中查找指定元素的功能。

#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int x)
{
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
 
        // 如果 x 在中间
        if (arr[mid] == x)
            return mid;
 
        // 如果 x 大于中间元素，只需要在右半部分搜索
        if (arr[mid] < x)
            left = mid + 1;
 
        // 如果 x 小于中间元素，只需要在左半部分搜索
        else
            right = mid - 1;
    }
 
    // 如果 x 没有在数组中找到，返回 -1
    return -1;
}
 
int main()
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        cout << "元素不在数组中！";
    else
        cout << "元素在数组中的索引为：" << result;
    return 0;
}

在上面的代码中，`binarySearch` 函数是实现二分查找的主要函数。该函数接受四个参数：要搜索的数组 `arr`，搜索范围的左边界 `left`，搜索范围的右边界 `right`，以及要查找的元素 `x`。

函数使用一个 while 循环来查找元素，只要搜索范围还没有缩小到只包含一个元素，就继续执行循环。在每次循环中，函数会计算搜索范围的中间位置 `mid`。然后，函数会检查中间位置的元素是否等于要查找的元素。如果是，函数会返回中间位置的索引。

如果中间位置的元素小于要查找的元素，那么要查找的元素只可能出现在中间位置的右侧。因此，函数会将搜索范围的左边界移到中间位置的右边一位。如果中间位置的元素大于要查找的元素，那么要查找的元素只可能出现在中间位置的左侧。因此，函数会将搜索范围的右边界移到中间位置的左边一位。

如果在循环结束时还没有找到要查找的元素，函数会返回 -1，表示元素不在数组中。否则，函数会返回要查找的元素在数组中的索引。