[lower_bound] cpp, python, scala

lower_bound는 정렬된 배열에서 찾고자 하는 key 이상 의 위치를 반환해준다.

찾고자 하는 key 이상 이기 때문에 입력이 [1, 2, 2, 2, 2, 2, 2, 3, 4, 5]일 때 2를 검색하면 index가 1이 될수도 다른 값이 될 수도 있다.

아래는 C++ , Python , Scala 의 결과를 보여준다.

C++

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
    vector<int> lst = { 1,1,2,2,3,3,4,4,5,5 };
    for (int i = 1; i <= 5; i++) {
        auto it = std::lower_bound(lst.begin(), lst.end(), i);
        cout << it - lst.begin() << endl;
    }
}

0 2 4 6 8

Python

import bisect

lst = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
for i in range(1,6):
    idx = bisect.bisect_left(lst, i)
    print(idx)

0 2 4 6 8

scala

@main
def Main(args: String*): Unit = {
  var lst = Array(1,1,2,2,3,3,4,4,5,5)
  for(i<-1 to 5){
    var idx = lst.search(i).insertionPoint
    println(idx)
  }
}

1 2 4 7 8

위에서 볼 수 있듯이 scala 는 항상 왼쪽을 보장하지 않는다.
(이진탐색하면서 일치하면 바로 반환하는 듯)