[알고리즘] 선형, 이진 탐색

1. 선형 탐색

• 처음부터 끝까지 혹은 끝부분부터 처음까지 하나씩 돌면서 검색하는 것 (indexOf, includes, find, findIndex 등등...)
• 시간 복잡도는 O(n)이다. for루프 한 개.

2. 이진 탐색

• 이진 탐색의 경우 확인을 할 때마다 남은 항목의 절반을 없앨 수 있다.
• 정렬이 되어 있어야 한다. (ex. 가장 작은 수 ~ 가장 큰 수) //가장 중요!!
• 시간 복잡도는 O(1)~O(logn)이다. 
• 중간 지점 기준으로 찾는다. 중간 지점보다 크다면 중간 오른쪽. 거기서 또 새로운 중간 지점을 찾으면서 반복한다.

function binarySearch(arr, val) {
    let start = 0;
    let end = arr.length - 1;
    let middle = Math.floor((start + end) / 2); // 중간에서 내림하거나 올림
    /* 원하는 값을 찾지 못할경우를 대비해서 start와 end값이 같아질 때 멈추도록 설정 */
    while(arr[middle] !== val && start <= end) {
        if(val < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    if(arr[middle] === val){
        return middle;
    }
    return -1;
}