一.二分查找

int binarySearch(vector<int>& arr, int target) {
        int left = 0;
        int right = int(arr.size()) - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                // 根据题意补充代码
                return mid;
            }
            if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // left 是插入点
        return left;
}

二.二分查找（有重复值最左边）

#include <iostream>
#include <vector>

bool fun1(int x) {
    // 示例条件，可以根据实际需求修改
    return x <= 6;
}

int findLastTrue(const std::vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;
    int result = -1;  // 用于存储最后一个满足条件的元素下标

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (fun1(arr[mid])) {
            result = mid;  // 记录当前满足条件的位置
            left = mid + 1; // 继续搜索右半部分
        } else {
            right = mid - 1; // 搜索左半部分
        }
    }

    return result;  // 返回最后一个满足条件的元素下标
}

int main() {
    std::vector<int> arr = {1, 2, 3, 5, 5, 5, 7, 8, 9};
    
    int index = findLastTrue(arr);
    
    if (index != -1) {
        std::cout << "最后一个满足 fun1(x) 为 true 的元素在下标: " << index << ", 值为: " << arr[index] << std::endl;
    } else {
        std::cout << "没有找到满足条件的元素。" << std::endl;
    }

    return 0;
}

三.二分查找（有重复值最右边）


#include <iostream>
#include <vector>

bool fun1(int x) {
    // 示例条件，可以根据实际需求修改
    return x >= 4;
}

int findFirstTrue(const std::vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;
    int result = -1;  // 用于存储最后一个满足条件的元素下标

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (fun1(arr[mid])) {
            result = mid;  // 记录当前满足条件的位置
            right = mid - 1;
             // 继续搜索左半部分
        } else {
            left = mid + 1;// 搜索右半部分
        }
    }

    return result;  // 返回最后一个满足条件的元素下标
}

int main() {
    std::vector<int> arr = {1, 2, 3, 5, 5, 5, 7, 8, 9};
    
    int index = findFirstTrue(arr);
    
    if (index != -1) {
        std::cout << "最后一个满足 fun1(x) 为 true 的元素在下标: " << index << ", 值为: " << arr[index] << std::endl;
    } else {
        std::cout << "没有找到满足条件的元素。" << std::endl;
    }

    return 0;
}

c++