Binary Search

이진 탐색

- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

- 이진 탐색이라고 부른다.

- 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점을 가지고 찾으려는 데이터와 중간점위치에 있는 데이터를 반복적으로 비교해서 찾아가는 과정.

 

* 이진탐색의 시간복잡도는 O(logN)이다. 절반식 줄어들도록 만드는 점에서 퀵 정렬과의 공통점이 있다.  코테에서의 이진탐색이 쓰이는 경우에는 탐색 범위가 클 경우 이진탐색의 접근을 생각해보면 된다. 

 

- 재귀

function binarySearch(array,target,start,end){
  if(start>end){
    return null;
  }
  let mid = Math.floor((end+start)/2);
  if(target == array[mid]){
    return mid;
  }
  else if(target < array[mid]){
    return binarySearch(array,target,start,mid-1);
  }
  else{
    return binarySearch(array,target,mid+1,end);
  }
}

let t = [1,3,6,8,10,12,15];
console.log(binarySearch(t,10,0,t.length-1));

위의 소스코드를 살펴보면 재귀함수를 사용하여서 이용하였는데 반복문을 이용하여서도 이진탐색함수를 만들어낼 수 있다.

 

- 반복

function binarySearch(array,target,start,end){
  while(start<=end){
    let mid = Math.floor((end+start)/2);
    if(target == array[mid]){
      return mid;
    }
    else if(target < array[mid]){
      end = mid -1;
    }
    else{
      start = mid +1;
    }
  }
  return;
}

 

*이진탐색 트리 - 트리 자료 구조 중에서 가장 간단한 형태가 이진 탐색 트리이다.

 

이진탐색트리의 특징 

1. 부모노드보다 왼쪽 자식 노드가 작다.
2. 부모노드보다 오른쪽 자식 노드가 크다.

코테에서의 이진탐색문제들은 파라메트릭 서치 유형의 문제를 예로 들 수 있다.

 

파라매트릭 서치

Parametric Search는 이분 탐색과 유사하다. 파라매트릭 서치는 최적화 문제를 결정 문제로 바꾸어 푸는것이라고 한다. 

예시로 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제이면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀 나갈 수 있다.

 

예시로 롤러코스터를 탈 수 있는 사람들중에서 가장 어린 사람을 찾을때 롤러코스터를 탈 수 있는 사람은 7살 이상이라고 가정하고 가장 어린 사람의 번호는 몇번인지 찾아야한다. 이 문제를 결정 문제로 바꾸면 롤러코스터를 탈 수 있는가?이다. 

 

이제 사람들의 나이가 배열로 되어있고 1~9중에서 5번이 롤러코스터를 탈 수 없을경우 6번부터 9번까지 살펴보고 7번에게 결정문제를 주어지는 식으로 정답을 찾아간다.

 

* 이분탐색문제와의 차이점? 결정 문제인지 아닌지의 차이