查找算法

📕 第三部分：查找算法

---

第14讲：顺序查找与二分查找

🔑 知识点讲解

1. 顺序查找（线性查找）
    从头到尾逐个比较
    时间：O(n)
    适用：无序数组

2. 二分查找（折半查找）
    前提：数组必须有序
    每次取中间元素比较，将搜索范围缩小一半
   时间：O(logn)

    关键细节（面试爱问）：
    - mid = left + (right - left) / 2  （防溢出，不要写(left+right)/2）
   - 循环条件：left <= right
   - 找到返回下标，找不到返回 -1

二分查找的变体（重点）：
    - 查找第一个等于target的位置
    - 查找最后一个等于target的位置
    - 查找第一个大于等于target的位置
    - 查找最后一个小于等于target的位置

✏️ 练习：二分查找及其变体

#include <stdio.h>

// 标准二分查找
int binarySearch(int a[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 查找第一个等于target的位置
int findFirst(int a[], int n, int target) {
    int left = 0, right = n - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) {
            result = mid;
            right = mid - 1;  // 继续往左找
        } else if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

// 查找最后一个等于target的位置
int findLast(int a[], int n, int target) {
    int left = 0, right = n - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) {
            result = mid;
            left = mid + 1;  // 继续往右找
        } else if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

int main() {
    int a[] = {1, 3, 3, 3, 5, 7, 9};
    int n = 7;
    
    printf("查找3的位置: %d\n", binarySearch(a, n, 3));
    printf("第一个3的位置: %d\n", findFirst(a, n, 3));
    printf("最后一个3的位置: %d\n", findLast(a, n, 3));
    
    return 0;
}

输出：

查找3的位置: 2
第一个3的位置: 1
最后一个3的位置: 3