[이분검색]

문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

▣ 입력설명
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

▣ 출력설명
첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

▣ 입력예제 1
8 32
23 87 65 12 57 32 99 81

▣ 출력예제 1 3

---

결과

O

내가 푼 방식

- indexOf를 사용해 풀었지만 문제의 의도와 다름 

 

 

모범답안

function solution(target, arr){
    let answer;
    arr.sort((a, b)=>a-b);
    let lt=0, rt=arr.length-1;
    while(lt<=rt){
        let mid=parseInt((lt+rt)/2);
        if(arr[mid]===target){
            answer=mid+1;
            break;
        }
        else if(arr[mid]>target) rt=mid-1;
        else lt=mid+1;
    }

    return answer;
}

리뷰

문제는 일반적인 순회에서 O(n) 시간 복잡도를 가질 것을 이분검색으로 logn 번으로 감소 시킬 수 있는지 묻고 있다.

1. 인자로 받은 arr를 sort 함수로 오름 차순으로 정렬을 시킨다(이분검색은 정렬이 전제조건이다)

2. 양 쪽 끝의 인덱스에 lt와 rt라는 포인트를 둔다. 

3. while문을 통해 lt가 rt보다 같거나 작을 때만 순회하게 한다.

4. white문 안에 lt와 rt의 중간지점인 mid 값을 설정하고(내림)

5. 조건문을 통해 arr[mid] 값과 인자로 받은 target값을 비교한다.

6. 같을 때 answer의 값에 mid값 + 1을 할당하고 끝낸다(몇 번째 이므로 +1)

7. arr[mid]값이 target보다 클때는 mid이후 부터는 더 조회할 필요가 없으므로 rt의 포인터를 mid -1로 옮긴다. 

8. 작을 때는 그 반대로 lt의 포인터를 mid + 1로 옮긴다.