수정 된 이진 검색

Question

나는 배열이있는 문제를 해결하려고 노력해 왔습니다. A [] = {5,9,11,15}; 값이있는 2 개의 변수는 2와 10을 말합니다 .i 배열의 요소가 (2,10) 즉 2 (제외)에서 10 (포함) 사이의 값을 가지는지 알아야합니다. 단순히 루프를 돌릴 수 있고 여부를 검색> if (2 = A [i]) <하지만 배열 크기의 큰 값에서 일하는이 실 거예요 10^5 말할 수 있습니다. 또한 인덱스 값보다 작거나 값을 반환하는 수정 된 이진 검색을 사용하여 시도했다. 키 제공하지만 누군가가이 일을 위해 빠른 너 한테 나에게 제공 .can 실패 편집 : 여기에 POS breaaking 요소의 수는이 배열 FLOOR 함수가된다 (수정 바이너리)

int Floor(int A[], int l, int r, int key) 
{ 
int m; 
while(r - l > 1) 
{ 
    m = l + (r - l)/2; 

    if(A[m] <= key) 
     l = m; 
    else 
     r = m; 
} 

return l; 

}

int Floor (int A [], int si ZE, INT 키) 검사

{// 오류

경우 (키 < A [0]) 복귀 -1; // 당신은 단순히 당신에게 모든 값을 포함하는 범위를 반환 std::lower_bound을 사용할 수 있습니다

//

int ret=Floor(breaaking,pos,mini); 

printf("%d\n",ret); 

    printf("mini is %d and maxi is %d",mini,maxi); 

    if(pos==0) 
{ 
    printf("There is no breaking point in the array :) (pos==0)\n"); 
    printf("Yes\n"); 
} 
else if(ret==-1) 
{ 
    printf("Mini is smaller than smallest element of breaking\n"); 

     if(breaaking[0]<maxi) 
     { 

      printf("but maxi is greater than smallest element hece it lies between so:\n"); 
      printf("No\n"); 
     } 
    else { 
       printf("even maxi is less than smallest element hence:\n"); 
       printf("Yes\n"); 
      } 
} 
else if(ret==pos-1) 
{ 
    printf("mini is either equal to last element of breaker set or greater than it\n"); 

     if(mini==breaaking[pos-1]) 
     { 
      printf("mini is equal to the last element hence\n");  
        printf("No\n");} 
    else 
     { 
     printf("mini is greater than the last element hence:"); 
     printf("Yes\n"); 
     } 
} 
else 
{ 
    printf("returned a valid index which is less than or equal to mini which is btw %d\n",ret); 

     if(breaaking[ret]==mini) 
     { 
       printf("mini was equal to one of the element of array hence\n"); 
       printf("No\n"); 
     } 
    else 
    { printf("mini is smaller than this element but greater than next element\n"); 
     if(breaaking[ret+1]<maxi) 
      { 
       printf("next element lies between mini and maxi hence:\n") ;  
       printf("No\n"); 
      } 
     else 
      { printf("even maxi is smaller than next element hence\n"); 
       printf("Yes\n"); 
      } 
    } 
`} 

Answer 1

에는 바닥 값

return Floor(A, 0, size, key); 

에게}이 없습니다. 범위가없는 경우 범위는 비어 있습니다.

#include <iostream> 
#include <algorithm> 
#include <tuple> 

template<typename ForwardIterator> 
std::pair<ForwardIterator, ForwardIterator> 
range_inside(ForwardIterator b, ForwardIterator end, 
        int lower, int upper) { 
    auto it = std::lower_bound(b, end, lower); 
    auto it2 = std::upper_bound(it, end, upper); 
    return std::make_pair(it, it2); 
} 

int main() 
{ 
    int arr[] = { 2, 5, 9, 10, 11, 15}; 
    int *r, *e; 
    std::tie(r, e) = range_inside(std::begin(arr), std::end(arr), 2, 10); 
    std::for_each(r, e, [] (int& x) { std::cout << x << " "; }); 
    // output: 2 5 9 

    return 0; 
}