CS)이진탐색(vs indexOf)

이진탐색

정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘이다.

정렬된 배열(Ordered Array)
정렬된 배열이란 오름차순 또는 내림차순으로 정렬된 배열을 의미한다.

배열의 중간 값을 찾아서 찾고자 하는 값과 비교한다.
(arr[middle] === searchValue)
찾고자 하는 값이 중간값보다 작으면 중간값을 기준으로 왼쪽을 탐색(상한선을 당긴다.)
(searchValue < arr[middle] ? end = middle -1)
찾고자 하는 값이 중간값보다 크면 중간값을 기준으로 오른쪽을 탐색(하한선을 당긴다.)
(searchValue > arr[middle] ? start = middle +1)
찾고자 하는 값이 중간값과 같으면 해당 index를 리턴
찾고자 하는 값이 없으면 -1을 리턴

const orderedArray = [1,4,5,9,15,19,22,24,29,45,56,88,104,202,508,1024,8852,11042,12000,15000,20000,30333,40000,58245,60994,71114,88088,95642,106782];

const binarySearch = (arr,searchValue) => {
    let start = 0;
    let end = arr.length - 1;
    let middle
    let count = 0;
    while(start <= end) {
        middle = Math.floor((start + end) / 2);
        if(arr[middle] === searchValue) {
            console.log('while loop count: ',count); // 4;
            console.log('found at index: ',middle); // 28
            console.log('arr[middle] is ',arr[middle]); // 106782
            return middle;
        }
        else if(arr[middle] < searchValue) {
            start = middle + 1;
        }
        else if(arr[middle] > searchValue) {
            end = middle - 1;
        }
        count++;
    }
    
    return -1;
}

console.log(binarySearch(orderedArray,106782));

자바스크립트의 indexOf는 선형 탐색(linear search)이므로 이진 탐색보다는 이론적으로 속도가 느리지만 실 사용은 케이스마다 다르다.

예를 들어, 정렬되지 않은 배열데이터를 sort() 메서드를 사용한 뒤 이진탐색을 진행하는 경우는 선형 탐색의 속도가 압도적으로 빠르며, 작은 데이터(100개 정도의 요소를 가진 배열) 같은 경우 정렬되지 않았다 하더라도 indexOf의 속도가 더 빠르다.
요소가 100개이든, 1000개이든 이진 탐색이 선형 탐색보다 무조건 빨라야 되지 않나 싶었지만,
생각해보면 찾고자하는 요소의 위치에 따른 오차범위에 따라 중간값에 따라 달라지기 때문에 평균 속도에서 선형 탐색보다 느려지는 것 같다.

binarySearch vs indexOf의 속도는 아래의 포스트를 참조하였다.
https://medium.com/@nathanbell09/binary-search-vs-indexof-63651f91acb7

적은 요소를 가진 정렬된 배열에 대한 이진 탐색이 왜 선형 탐색보다 느린지에 대한 많은 답들이 존재한다.
https://www.sololearn.com/Discuss/2363509/solved-why-is-binary-search-slower-than-linear-search-for-a-list-of-100-binary-sorted-numbers