Hee's Story

Binary Search : lower bound & upper bound Binary Search (이진 탐색) 이진 탐색은 정렬이 된 데이터에서 어떠한 특정 값이 존재하는지 검색하는 알고리즘이다. 기준 값을 구해서 그 값을 기준으로 데이터를 나눠서 검색하는 방법이다. 특정 값을 찾을 때는 기본 이진 탐색으로 쉽게 구할 수 있다. 하지만 중복된 데이터에서 탐색할 때는 조금 더 응용된 방법을 사용해야한다. (예를 들어, 중복 된 데이터에서 특정 데이터가 몇 개가 존재하는지 등) 따라서 lower bound와 upper bound를 구해야한다. Lower bound는 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치를 리턴해준다. High Bound는 특정 값보다 처음으로 큰 값이나 나오는 위치..