二分搜索

对于一个有序序列，我们可以用二分搜索的方式在该序列中搜索某个数值。

以升序序列为例，二分搜索首先确定搜索的范围（即搜索序列的第一个元素的位置 left 和最后一个元素的位置 right），然后计算出中间位置 mid。比如我们要搜索的序列是：2, 7, 11, 19, 23, 31, 33, 39。在初始的状态下，搜索范围是整个序列，那么第一个元素的位置left就是1，最后一个元素的位置right就是8，mid = (left + right)/2 = 4（注意序列的长度是偶数，left+right的和是奇数，这里对结果进行了向下取整）。

接下来，检查中间位置的元素是否是要搜索的值 target（假设我们要搜索的值是31，那么target就等于31），如果不是，则比较中间元素与 target 的大小关系：如果中间位置的元素比target大，因为序列是升序的，所以 target 只可能在中间元素的左侧，也就是位于 left 和 mid - 1之间，此时把 right 更新为 mid - 1，也就是说，下一次我们要搜索的范围的右边界发生了变化。更新right后，再次计算新的mid，重复上面的搜索过程；如果中间位置的元素比 target 小，那么 target 只可能位于 mid + 1 和 r 之间，此时把 l 更新为 mid + 1（这种情况是左边界发生了变化）后，重复上面的搜索过程。

在搜索过程中，一旦发现某一次，搜索范围中间的值等于target，那么就是找到了目标值；或者始终找不到的情况下，当left > right的时候，我们就知道target不在我们搜索的序列中，此时搜索也就结束了。

以在序列（2, 7, 11, 19, 23, 31, 33, 39）中搜索31为例，说明一下二分搜索的流程。
第一轮搜索：left = 1，right = 8（注意在大多数编程语言中，数组下标是从0开始的），mid = (1 + 8) / 2 = 4，序列中第四个元素是19，19小于要搜索的目标值31，因此31只可能在序列的后半段，此时更新左侧边界left，把left赋值为mid + 1，此时left变成了5；
第二轮搜索：left = 5，right = 8，mid = (5 + 8) / 2 = 6，序列中第6个元素是31，此时找到了目标元素，其在序列中的位置是6，搜索结束。

再以要搜索的值是30为例，我们从刚才的第二轮搜索继续。到了上面的第二轮搜索，序列中第6个元素是31，大于30，那么30只可能存在于第5个元素（left的值为5）的右侧、31（第6个元素）的左侧，此时更新right，将其赋值为mid - 1，此时right变成了5。继续进行第三轮搜索。
第三轮搜索：left = 5，right = 5，mid = (5 + 5) / 2 = 5。序列中第5个元素是23，小于30，此时更新left为mid + 1，left的值变为6，继续进行第四轮搜索。
第四轮搜索：在进行搜索前，发现left的值已经大于right，这时可以确定要搜索的值不在序列中，搜索结束。

#include
# include 
using namespace std;

int main() {
    int n;
    cin >> n;
    vector nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int V;
    cin >> V;

    int left = 0, right = n - 1;
    int pos = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == V) {
            pos = mid + 1;  // 位置从1开始编号，所以加1
            break;
        } else if (nums[mid] < V) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    if (pos != -1) {
        cout << pos << endl;
    } else {
        cout << "Value not found." << endl;
    }

    return 0;
}