1. 이진 탐색 알고리즘 이해하기

1. 순차탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 부터 하나씩 확인한다.
• 탐색을 위한 시간 복잡도 : O(N)

2. 이진탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.
• 시작점(left)와 끝점(end)을 기준으로 탐색
• 탐색을 위한 시간 복잡도 : O(logN)
• 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우
• 데이터를 정렬한 뒤에 다수의 쿼리를 날려야 하는 경우

3. 이진 탐색 코드 예시(재귀 함수)

function binarySearch(arr,target,start,end){
    if(start>end) return -1;
    let mid = parseIng((start+end)/2);
    //찾은 경우 중간점 인덱스 반환
    if(arr[mid]===target) return mid;
    //중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽을 확인
    else if(arr[mid]>target) return binarySearch(arr,target,start,mid-1);
    //중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽을 확인
    else return binarySearch(arr,target,mid+1, end);
}

let n=10;
let target=7;
arr=[1,3,5,7,9,11,13,15,17,19];

let result = binarySearch(arr,target,0,n-1);
if(result===-1) console.log("원소가 존재하지 않습니다")
else console.log(`${result+1}번째 원소입니다`)

4.이진 탐색 코드 예시(반복문)

function binarySearch(arr,target,start,end){
    while(start<=end){
        let mid = parseInt((start+end)/2);
        //찾은 경우 중간점 인덱스 반환
        if(arr[mid]===target) return mid;
        //중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        else if(arr[mid>target]) end = mid-1;
        //중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else start=mid+1
    }
    return -1
}

let n =10;
let target=7;
arr =[1,3,5,7,9,11,13,15,17,19]
let result = binarySearch(arr,target,0,n-1);
if(result===-1) console.log("원소가 존재하지 않습니다");
else console.log(`${result+1}번째 원소입니다`)