대상보다 작거나 같은 배열에서 최대 수 찾기

Question

이것이 내가하는 일입니다. 배열 (또는 벡터), V가 있고 오름차순으로 정렬하고 있습니다. 이상 또는 위치 i에있을 것입니다 a을 대상으로하는 동일 적은. (처음 i = 0)

while (V[i] <= a && i < V.size()) { i++; } 
i--; 

내가 Codechef에 대한 질문에 코드의이 부분을 사용하고 AC를 얻고는, 그러나 이전에 가장 많은 수의 I 이것을 사용하고 그것을 잘못하고 있었다.

while (V[i+1] <= a && i < V.size()-1) i++; 

둘은 본질적으로 동일한 작업을 수행하지 않습니까? 왜 내가 처음이 아닌 두 번째로 WA를 얻는거야? 그들이 다른 테스트 케이스를 지적 해 주시겠습니까? 테스트 케이스, 예를 들어

:

V =

i = 2 함께 = 11

양단부 5,7,10,12.

내가 얻고 또 다른 유사한 문제

이있다 : I 정렬 된 값의 또 다른 목록을

내가 통과하고 V2를 말한다. 각 값 x에 대해 x보다 작거나 같은 V에서 가장 높은 숫자를 찾으려고합니다.

while (V[i] <= x && i < V.size()) { 
     i++; 
    } 
i--; 

V2를 통해 반복 할 때마다, 내가 영으로 난의 값을 설정하지 않은 대신 내가 전에 어디에서 계속 :이 내가 이전에하던 것입니다.

을 (V2 정렬 되었기 때문에) 내가 가진 그래서 경우 :

V = 5 7 10 12

V2 = 7 8 10 11 13

내 코드는 인덱스 1을 반환

, 1, 2, 2, 3. 그럼에도 불구하고 나는 이것을 가지고 WA를 얻고 있었다. :/

하지만 V2를 반복 할 때마다 i = 0으로 할 때 AC를 얻었습니다. 이제는 느리게 진행되는데, 처음에하고 싶지 않았지만, i를 0으로 재설정하지 않으면 왜 작동하지 않는지 전혀 알 수 없습니다.

도움말, 얘들 아? : 3

편집 : 여기서 값을 바꿀 수 있습니다.

vector <int> V1 = {1,2,3}; 
int target = 5; 
int index = 0; 
while (V1[index] <= target && index < V1.size()) { index++; } 
index--; 
cout << index << endl; 
index = 0; 
while (V1[index+1] <= target && index < V1.size()-1) index++; 
cout << index << endl; 

이 질문은 항상 제공된 각 테스트 케이스에 대해 동일한 대답을 반환하는 것으로 보입니다.

Answer 1

검색 할 배열이 이미 정렬되었으므로 다양한 이진 검색 알고리즘 함수를 사용하여 올바른 값을 찾을 수 있습니다. 이진 검색을 사용하면 O(n)이라는 사용중인 검색과는 달리 값을 찾기 위해 복잡성이 O(log n)입니다.

정렬 된 배열에 백만 개의 숫자가 있으면 적절한 값을 찾기 위해 하나씩 검색하면 최대 백만 번 비교할 수 있습니다. 이진 탐색을 사용하면 최대 20 개의 비교가 수행됩니다. 비교는 축소 시퀀스의 중간 요소에서만 수행됩니다 (시퀀스가 번호를 찾을 수 없을 때마다 반으로 잘라 짐).

<algorithm>에는 이진 검색을 수행하는 데 사용할 수있는 std::upper_bound이 있습니다. 트릭은 std::upper_bound이 반환하는 반복기 앞에 오는 값을 반환하고 검색 할 값의 하단에 범위를 벗어나지 않도록하는 것입니다.

#include <iostream> 
#include <algorithm> 

int getIndex(const std::vector<int>& V, int val) 
{ 
    auto iter = std::upper_bound(V.begin(), V.end(), val); 
    if (iter != V.begin()) 
     // return the index of the item before the found item 
     return std::distance(V.begin(), std::prev(iter)); 

    // return the first item 
    return 0; 
} 

int main() 
{ 
    std::vector<int> V = {5,7,10,12}; 
    std::vector<int> V2 = {7, 8, 10, 11, 13}; 
    std::for_each(V2.begin(), V2.end(), [&](int val) 
    {std::cout << getIndex(V, val) << " ";}); 
} 

찾을 값이 벡터의 모든 값보다 작은 경우의 예는 확인하지 않습니다

See Live Example

참고. 이 검사를 추가하고 숫자가 범위를 벗어 났음을 나타내는 값을 반환해야합니다.