二分查找算法

二分查找的思想就一个：逐渐缩小搜索区间。如下图所示，left 和 right 向中间走，直到直到它们重合在一起。

二分查找算法（Binary Search）是一种在有序数组中查找目标元素的高效算法。以下是其基本思想和实现：

1、首先，确定查找范围的左右边界，通常为数组的起始和结束位置。

2、计算中间元素的索引，将其与目标元素进行比较。

3、如果中间元素等于目标元素，查找成功，返回索引。

4、如果中间元素大于目标元素，说明目标元素可能在左半部分，将右边界移动到中间元素的左侧。

5、如果中间元素小于目标元素，说明目标元素可能在右半部分，将左边界移动到中间元素的右侧。

6、重复步骤2-5，直到找到目标元素或者左边界超过右边界，表示查找失败。

【输入描述】

输入三行。第一行是数组大小 n ，第二是数组元素，用空格分开；第三行是要查找的元素。

【输出描述】

输出若一行，输出查找元素在已排序数组中的下标，如果不在数组中输出 -1 。

【输入样例】

8
7 13 4 5 8 1 11 9
5
【输出样例】

2
【参考程序】

// 小牛编程
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10001;
int arr[MAXN];

// 二分查找算法
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        //取中心时靠近左端点
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

int main() {
    int n, target;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 先排序
    sort(arr, arr + n);

    cin >> target;
    cout << binarySearch(arr, n, target);

    return 0;
}

经典算法

二分查找算法