문제 : binarySearch

오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수

인자 2 : target

• number 타입의 정수

출력

• number 타입을 리턴해야 합니다.

주의사항

• 이진탐색 알고리즘(O(logN))을 사용해야 합니다.
• 단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다.
• target이 없는 경우, -1을 리턴해야 합니다.

입출력 예시

let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output); // --> 2

output = binarySearch([4, 5, 6, 9], 100);
console.log(output); // --> -1

풀이

const binarySearch = function (arr, target) {
    let start = 0;  // 배열의 시작 지점
    let end = arr.length - 1;   // 배열의 마지막 지점
    let mid;    // 배열의 중간값
    while (start <= end) {  // 시작값과 마지막값이 같아질경우 답이 없으므로 반복문을 빠져나와서 -1 리턴
        mid = Math.floor((start + end) / 2) // 중간값은 시작값(인덱스) + 마지막값(인덱스) / 2
        console.log(`중간값 : ${mid}`)
        if (arr[mid] === target) {  // 만약에 배열에 중간값이 찾고자하는 값과 같다면
            return mid; //해당 인덱스 반환
        } else if (arr[mid] > target) { // 중간값이 찾고자하는 값보다 크다면 (반나눈거에서 아랫쪽에 있다는 뜻)
            end = mid - 1;  // 마지막 값을 중간값 -1로 해서 다음 반복을 시작한다
        } else {    //  중간값이 찾고자 하는 값보다 작다면 (반 나눈거에서 위쪽에 있다는 뜻)
            start = mid + 1;    // 시작값을 중간값+1 해서 다음 반복을 시작한다
        }
    }
    return -1;
};