[알고리즘] 이진검색(Binary Search) + 순위(Rank)확인 시스템(?)

 

오름차순or 내림차순으로 정렬되어 배열이 있다고 하고,

정렬 되어 있는 배열에 특정값이 몇번 인덱스에 있는지 찾는 이진검색 알고리즘이 존재한다.

 

 

 

변수명 arr 배열(오름차순)을 넣고 15을 찾는다면

 

 

변수명 arr2배열에 주석부분을 서로 바꿔준 뒤 마찬가지로 15을 찾으면

 

 

 

사실 여기까지는 인터넷에 찾아보면 더 자세한 설명도 많이 나온다. 근데 내가 글을 쓴 이유는

 

 

순위 시스템에서 새로운 점수를 받았을때 해당 점수가 등수에 반영 가능한 여부를 판단하기 위해서 이다.

 

그러기 위해 이진검색을 조금 변경 해보았다.

 

 

내림차순인 변수명 arr2 배열에서 targetValue 새로운 점수인 70점이 순위에 드는지 여부를 확인하기 위함이다.

결과이다.

 

출력에 result+1은 실제 배열 인덱스와 우리가 인식하는 등수(1위부터시작)하기 때문에 +1 해주었다.

 

1점을 넣으면

 

이미 순위에 존재하는 67을 넣으면

 

 

 

이러하다.

 

 

자세한 시간복잡도 설명을 넣을수도 있는데 그러기보단

 

 

배열을 늘려 100개의 점수를 넣고

 

함수내에 while문이 1번 돌때 카운트 변수를 넣고 세보았다.

 

55점이라는 점수를 찾으려 할때, 5번만에 46등인지를 알아냈다.

 

 

만약에 1등부터 100등까지 첫번째칸부터 점진적으로 검사 했더라면(선형 탐색법이라더라),  물론 더 빨리 찾을수도 있지만(100점이라던가 99점이라던가), 반대로 99번을 검사할수도 있다..!!!

 

예를들어 랭킹에 반영 불가능한 점수는 99번 반복문을 끝을 다 돌아도 못찾았다는걸 알겠지만,

여기서는 7번만에 등수조차 안든다는 것을 알아낼수도 있다.

 

 

끝.

 

 

 

2020.09.13 수정------------------------------

 

중복 점수에 대한 체크가 제대로 되지 않는다는 피드백을 받았다.(ex 70점 3개가 있다면 제일 앞에 있는 70점 위치를 가르키지 못함.) 그러므로 기존에 같은점수가 순위에 이미  있다면, 탈출하는 부분을 제거하였다.