关于C++和Python二分查找库函数应用于二维数组的总结

Python

bisect_left

• 功能：找到插入位置，使得插入后的数组仍然有序。

• 语法：

  bisect.bisect_left(a, x, lo=0, hi=len(a))
  

  • a：待搜索的数组。
  • x：待插入的值。
  • lo：搜索的起始位置，默认为 0。
  • hi：搜索的结束位置，默认为数组的长度。

• 返回值：第一个不小于 x 的元素的位置。

bisect_right

• 功能：找到插入位置，使得插入后的数组仍然有序。

• 语法：

  bisect.bisect_right(a, x, lo=0, hi=len(a))
  

  • a：待搜索的数组。
  • x：待插入的值。
  • lo：搜索的起始位置，默认为 0。
  • hi：搜索的结束位置，默认为数组的长度。

• 返回值：第一个大于 x 的元素的位置。

C++

lower_bound

• 功能：找到范围内第一个不小于给定值的位置。

• 语法：

  std::lower_bound(first, last, value, comp)
  

  • first：范围的起始迭代器。
  • last：范围的结束迭代器。
  • value：待查找的值。
  • comp：自定义比较函数（可选）。

• 返回值：第一个不小于 value 的元素的迭代器。

upper_bound

• 功能：找到范围内第一个大于给定值的位置。

• 语法：

  std::upper_bound(first, last, value, comp)
  

  • first：范围的起始迭代器。
  • last：范围的结束迭代器。
  • value：待查找的值。
  • comp：自定义比较函数（可选）。

• 返回值：第一个大于 value 的元素的迭代器。

对二维数组进行比较

在 Python 和 C++ 中，通常需要自定义比较函数来比较二维数组的特定元素。

Python 示例

import bisect

def compare_second_element(a, x):
    return a[1] < x

a = [[1, 3], [2, 5], [3, 7], [4, 9]]
x = 6

# 使用 bisect_left 和自定义比较
index = bisect.bisect_left(a, x, key=lambda pair: pair[1])
print("Index:", index)

import bisect

# 自定义比较函数
def compare_second_element(x):
    return x[1]

# 二维数组
a = [[1, 3], [2, 5], [3, 7], [4, 9]]
x = 6

# 查找第一个大于x的第二个元素的位置
index = bisect.bisect_right(a, [0, x], key=compare_second_element)

print("Index:", index)
if index < len(a):
    print("Found element:", a[index])
else:
    print("Element not found.")

C++ 示例

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

int main() {
    vector<array<int, 3>> a = {
        {1, 3, 5},
        {2, 5, 6},
        {3, 7, 8},
        {4, 9, 10}
    };

    int value = 6;

    // 使用 lower_bound 查找
    auto it = lower_bound(a.begin(), a.end(), value, [](const array<int, 3>& v, const int& value) {
        return v[1] < value;
    });

    if (it != a.end()) {
        cout << "Found element: [" << (*it)[0] << ", " << (*it)[1] << ", " << (*it)[2] << "]" << endl;
    } else {
        cout << "Element not found." << endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

int main() {
    // 定义二维数组
    vector<array<int, 3>> a = {
        {1, 3, 5},
        {2, 5, 6},
        {3, 7, 8},
        {4, 9, 10}
    };

    int value = 6;

    // 使用 upper_bound 查找第一个大于 value 的元素位置
    auto it = upper_bound(a.begin(), a.end(), value, [](const int& value, const array<int, 3>& v) {
        return value < v[1];
    });

    // 输出结果
    if (it != a.end()) {
        cout << "Found element: [" << (*it)[0] << ", " << (*it)[1] << ", " << (*it)[2] << "]" << endl;
    } else {
        cout << "Element not found." << endl;
    }

    return 0;
}