猫史档案馆

/*二分查找是一种常用的查找算法，它适用于有序数组中的查找操作。它的原理是通过将数组分成两部分，然后判断目标值在哪一部分中，从而缩小查找范围，直到找到目标值或者确定目标值不存在。


那么，我们可以通过一个猜数字的游戏来解释二分查找算法。

假设你有一个1到100之间的整数，让你猜这个数字是多少。每次你猜一个数字，系统会告诉你猜的数字是太大了还是太小了，直到你猜中为止。

首先，我们将猜测的范围缩小到1到100的中间值，也就是50。然后，系统会告诉你猜的数字是太大了还是太小了。

如果系统告诉你猜的数字太大了，那么我们可以将猜测的范围缩小到1到50的中间值，也就是25。如果系统告诉你猜的数字太小了，那么我们可以将猜测的范围缩小到50到100的中间值，也就是75。

通过不断缩小猜测的范围，我们可以在每次猜测后将范围缩小一半，直到猜中目标数字。
这其实就是2分查找基本原理。

那么，使用2分查找的数组需要满足哪些条件？
数组要有序。这个相信都能理解。


*/

#include <iostream>
using namespace std;

// 二分查找函数
int binarySearch(int arr[], int target, int left, int right) {
    while (left <= right) {
        int mid = left + (right - left) / 2; // 计算中间位置

        if (arr[mid] == target) {
            return mid; // 找到目标值，返回索引
        }
        else if (arr[mid] < target) {
            left = mid + 1; // 目标值在右半部分，更新左边界
        }
        else {
            right = mid - 1; // 目标值在左半部分，更新右边界
        }
    }

    return -1; // 目标值不存在，返回-1
}

int main() {
    int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
    int target = 12;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = binarySearch(arr, target, 0, n - 1);

    if (result == -1) {
        cout << "目标值不存在" << endl;
    }
    else {
        cout << "目标值在数组中的索引为：" << result << endl;
    }

    return 0;
}

l

为啥要left<=right？因为左右区间一旦交叉，那么要么就说明找到了，要么说明整个数组无该元素，直接退出。

另外，如果需要对数组排序，可以用标准库的sort快速排序函数。

 

最后是一道2分查找的变形题目

【题目】

输入一个整数n，x,接下来输入n个整数，可能会重复。现在查找x，输出x在数组中第一次出现的位置（保证数组有目标元素x）

【样例输入】

5 4

1 2 3 4 4 

【样例输出】

4

【样例解释】

数组中有2个4，按照题目要求，输出第一个4出现位置，为4

本帖只是略解，有不懂的评论区或者直接查看知乎上这篇文章，讲的比较详细图文并茂带你入门二分查找算法 - 知乎 (zhihu.com)

int find(int x){
	int l=1,r=n*n;//这边r=数组长度哈（）
	while(l<r){
		int mid=l+(r-l)/2;
		if(arr[mid]>=x)r=mid;
		else l=mid+1;
	}
	return l;
}