[인프런 섹션7] 이분검색 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션7] 이분검색 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-27

1. 정렬된 상태에서 몇번째 위치인지 return

2. sort() 정렬 중 target을 발견하면 return i+1;

문제점
sort() 함수의 매개변수 중 index는 없다!
따라서 sort((a, b, i) => {}) 불가

3. 이분검색을 하지 않을 경우

• sort() 정렬 후 arr.indexOf(target)

4. 이분검색 구현

• left, right, mid
• left = 0, right = arr.length, mid = Math.floor((right+left)/2)

if (arr[mid] === target) return mid+1;
else if (arr[mid] < target) left = mid;
else if (arr[mid] > target) right = mid;

✍️소스코드

2021-06-27 이분검색 X

function solution(arr, target) {
    arr.sort((a, b) => a - b);
    return arr.indexOf(target) + 1;
}

2021-06-27 이분검색

function solution(arr, target) {
    arr.sort((a, b) => a - b);

    let left = 0, right = arr.length;
    while (true) {
        let mid = Math.floor((right + left) / 2);

        if (arr[mid] === target) return mid+1;
        else if (arr[mid] < target) left = mid;
        else if (arr[mid] > target) right = mid;
    }
}

놓친 것 3가지

• let left = 0, right = arr.length-1;
• while(left <= right)
• left = mid+1, right = mid-1;

function solution(arr, target) {
    arr.sort((a, b) => a - b);

    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((right + left) / 2);

        if (arr[mid] === target) return mid+1;
        else if (arr[mid] < target) left = mid+1;
        else if (arr[mid] > target) right = mid-1;
    }
}