(转载)C++ STL中的Binaray Search(二分查找)

一、常用操作

1、头文件

#include <algorithnm>

2、使用方法

(1)binary_search:查找某个元素是否出现

函数模板:binary_search(arr[ ], arr[ ] + size, index)

参数说明:

arr[ ]:数组首地址

size:数组元素个数

index:需要查找的数值

函数功能:在数组中以二分法检索的方式进行查找,若在数组(要求数组元素非递减)中查找到index元素则为真,若查找不到则返回假。

(2)lower_bound:查找第一个元素大于等于某个元素的位置

函数模板:lower_bound(arr[ ], arr[ ] + size, index)

参数说明:

arr[ ]:数组首地址

size:数组元素个数

index:需要查找的数值

函数功能:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于等于val的第一个元素。如果所有元素都小于val,则返回last的位置,且last的位置是越界的。

(3)upper_bound:查找第一个元素大于某个元素的位置

函数模板:upper_bound(arr[ ], arr[ ] + size, index)

参数说明同上

 

二、代码

#include <iostream>
#include <algorithm>
using namespace std;

int a[100] = { 4, 10, 11, 30, 69, 70, 96, 100 };
int binarySearch(int x, int n)//n是x数组的长度
{
    int left = 0;
    int right = n - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (x == a[mid])
            return mid;
        else if (x > a[mid])
            left = mid + 1;
        else if (x < a[mid])
            right = mid - 1;
    }
    return -1;//没有找到数据x
}

//二分搜索递归实现
int recurisonBinarySearch(int left, int right, int x)
{
    if (left > right)
        return -1;
    int mid = (left + right) / 2;
    if (x == a[mid])
        return mid;
    if (x > a[mid])
        return recurisonBinarySearch(mid + 1, right, x);
    else
        return recurisonBinarySearch(left, mid - 1, x);
}

int main()
{
    int b = binary_search(a, a + 9, 4);//这个是直接调用库函数
    int c = binary_search(a, a + 9, 40);
    int d = lower_bound(a, a + 9, 10) - a;
    int e = lower_bound(a, a + 9, 101) - a;
    int f = upper_bound(a, a + 9, 10) - a;
    int g = upper_bound(a, a + 9, 101) - a;
    return 0;
}

 

上一篇:分支界定法(branch and bound)与背包问题的代码实现


下一篇:C11特性:std::equal_range、std::lower_bound、std::min_element、获取迭代器在容器中的位置序号、std::distance