이진 탐색법

이진 탐색법이란

데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘

데이터 집합에서 원하는 데이터를 찾을 때까지 집합을 이분하여 탐색하는 방법

데이터 양이 많을 때 사용 시 효율적

 

정렬된 배열 안에서 특정 값의 유무를 파악 시 사용됨

 

이진 탐색법 조건

데이터가 반드시 순서대로 정렬된 상태여야 함

 

이진 탐색법 과정

1. 배열의 중간 값과 특정 값을 비교

2. 특정값이 중간 값보다 크다면 배열의 중간값 이하의 값을 제외한 배열을 만듦

3. 다시 특정값을 새로 만든 배열의 중간 값과 비교하여 작다면 중간 값보다 큰 값들을 제외하고 배열을 만듦

4. 위의 과정을 반복하여 특정값이 중간값과 일치하거나, 더 이상 배열을 새로 만들 수 없을 때 특정값의 유무를 확인

 

 

이진 탐색 코드

const binarySearch=(target, arr)=>{
  let low = 0;
  let high = arr.length-1;
  
  while(low<=high){
    
    let mid = Math.floor((low+high)/2);    
  
    if(target===arr[mid]){
       return mid;
    }else if(target>arr[mid]){
      low = mid+1 
    }else if(target<arr[mid]){
      high = mid-1
    }
  }
  return undefined;
}

/*
target = 43
arr = [17, 28, 43, 67, 88, 92, 100, 200]
*/

 

이진 탐색 시간 복잡도 및 빅오 표기

N개 크기의 배열에서 탐색과정을 거치면서 탐색할 배열의 크기가 반씩 줄어듦

 

Ex) 배열 : [17, 28, 43, 67, 88, 92, 100, 200]  찾는 값 : 17
중간 값 : 88 -> 작다 -> [17, 28, 43, 67]
중간 값 : 43 -> 작다 -> [17, 28]
중간 값 : 28 -> 작다 -> [17]
중간 값 : 17 -> 종료

 

배열의 크기가 8,4,2,1로 반씩 줄어듦

N = 8일 때 탐색이 3회 수행되었으므로 시간 복잡도 = 3

 

N개 크기의 배열을 이진 탐색 시 N, N/2, N/4, N/8, ..., 1으로 실행됨

이때 실행된 탐색 횟수 = 시간 복잡도 = K

2^K = N

K = log2N

 

즉, 이진 탐색의 시간 복잡도는 O(logN)

 

 

 

 

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제