ÇLOWER_BOUND的实现 [英] Implementation of C lower_bound

问题描述

基于以下定义

在这里找到

  

返回一个迭代器指向   在排序范围第一元件   [第一，最后），它不比较   比值以下。比较是   完成使用任何运营商的LT;为了   第一个版本，或者补偿第二。

什么是C相当于实施LOWER_BOUND的（）。据我所知，这将是二进制搜索的改进，但似乎无法十分精确定位到具体实施。

  INT LOWER_BOUND（INT A []，INT lowIndex，诠释upperIndex，诠释E）;
 

样品案例：

  INT一个[] = {2,2，2，7};

LOWER_BOUND（一，0，1,2）将返回0  - ＆GT; upperIndex是超越过去的包容性指数是用C ++签名的情况。

LOWER_BOUND（一，0，2,1）将返回0。

LOWER_BOUND（一，0，3,6）将返回3;
LOWER_BOUND（一，0，4,6）将返回3;
 

我试图code为如下：

  INT low_bound（INT低，诠释高，诠释E）
{
    如果（低℃，）返回0;
    如果（低＆GT; =高）
    {
      如果（E＆LT = A [小]）返回低;
      回到低+ 1;
    }
    INT中期=（低+高）/ 2;
    如果（E＆gt;在[MID]）
        返回low_bound（MID + 1，高，E）;
    返回low_bound（低，中，E）;

}
 

解决方案

LOWER_BOUND 几乎像做了通常的二进制搜索，除了：

1. 如果未找到该元素，你回到你的当前位置的搜索，而不是返回一些空值。
2. 如果找到该元素，你向左搜索，直到找到一个不匹配的元素。然后返回一个指针/迭代器的第一个匹配的元素。

是的，就是这么简单。 ： - ）

Based on the following definition found here

Returns an iterator pointing to the first element in the sorted range [first,last) which does not compare less than value. The comparison is done using either operator< for the first version, or comp for the second.

What would be the C equivalent implementation of lower_bound(). I understand that it would be a modification of binary search, but can't seem to quite pinpoint to exact implementation.

int lower_bound(int a[], int lowIndex, int upperIndex, int e);

Sample Case:

int a[]= {2,2, 2, 7 };

lower_bound(a, 0, 1,2) would return 0 --> upperIndex is one beyond the last inclusive index as is the case with C++ signature.

lower_bound(a, 0, 2,1) would return 0.

lower_bound(a, 0, 3,6) would return 3;
lower_bound(a, 0, 4,6) would return 3; 

My attempted code is given below:

int low_bound(int low, int high, int e)
{
    if ( low < 0) return 0;
    if (low>=high )
    {
      if ( e <= a[low] ) return low;
      return low+1;
    }
    int mid=(low+high)/2;
    if ( e> a[mid])
        return low_bound(mid+1,high,e);
    return low_bound(low,mid,e);

}

解决方案

lower_bound is almost like doing a usual binary search, except:

1. If the element isn't found, you return your current place in the search, rather than returning some null value.
2. If the element is found, you search leftward until you find a non-matching element. Then you return a pointer/iterator to the first matching element.

Yes, it's really that simple. :-)

这篇关于ÇLOWER_BOUND的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！