이진탐색, 알고리즘을 공부하면서 한 번은 거쳐가야 하는 관문이다.
이진탐색은 배열에 찾고자 하는 값이 있는지 빠르게 찾을 수 있다. 어떻게 이를 가능하게 하는지 살펴보도록 하겠다.

이진탐색 원리

이진탐색은 우선 오름차순이든 내림차순이든 잘 정렬되어 있는 데이터를 사용해야만 한다. 왜냐하면 이진탐색을 가능하게 하는 이유가 '어떤 위치에 있는 값은 다른 값들보다 크거나 작다'는 가정을 기반으로 하기 때문이다. 여기에서는 이왕이면 오름차순으로 정렬되어있는 데이터를 사용하려고 한다.

이진탐색은 탐색하고자 하는 배열을 두 부분으로 나누는 아이디어에서 시작된다. 이제 배열을 어떤 기준을 가지고 나눌 것이냐는 문제가 제시된다. 답은 바로 배열의 가운데를 정하는 것이다. 이 가운데 값이 찾고자 하는 값보다 크면, 큰 쪽에 있는 부분은 다음 탐색 대상에서 제외된다. 가운데 값이 찾고자 하는 값보다 작다면, 작은 쪽에 있는 부분이 탐색 대상에서 제외될 것이다.

구현

JavaScript로 구현하겠다.
입력값으로는 오름차순으로 정렬된 중복값이 없는 배열(arr)과 찾고자 하는 값(target)이 들어온다.
반환값으로는 찾고자하는 값이 있을 경우 index를 돌려주고 없을 경우는 -1을 반환한다.
다음과 같이 작성하였다.

const binarySearch = function (arr, target) {
	
  // 실제 작동하는 이진탐색 함수
  const aux = (arr, target, start, end)=>{
      if (start > end) return -1;

      let pivot = Math.round((start + end) / 2);
      // 1. target 값과 일치하는 값을 찾았을 경우
      if (arr[pivot] === target) return pivot;
      // 2. target 값이 현재 기준점의 값보다 작을 경우
      else if(arr[pivot] > target){
        end = pivot-1;
        return aux(arr, target, start, end);
      }
      // 3. target 값이 현재 기준점의 값보다 클 경우
      else{
        start = pivot+1;
        return aux(arr, target, start, end);
      }
    }
  
  // 초기값 세팅
  let start = 0;
  let end = arr.length - 1
  
  // 함수 호출
  return aux(arr, target, start, end);

};

나는 재귀 함수를 사용하여서 구현을 하였다.
재귀함수에 새롭게 놓는 start와 end는 현재 탐색 범위를 설정한다. '몇 번 인덱스부터(start) 몇 번 인덱스까지(end)의 탐색을 진행하고 있다'를 나타낸다.
재귀 함수의 종료 조건은 start가 end보다 커질 때로 정하였다. 그 때의 경우 결국 target에 해당하는 값을 찾지 못한 것이기 때문에 -1을 반환한다.

1. pivot은 새로 구역을 나눌 기준점이다. 그리고 현재 탐색에서 target과 비교할 값의 위치이기도 하다. 이 때 target의 값이 arr[pivot]과 같다면 pivot이 찾고자 하던 값의 위치를 나타내고 있기 때문에 pivot을 반환해준다.
2. 만약 pivot이 가리키는 값이 target보다 크다면 pivot보다 큰 위치에 있는 배열의 값들은 당연히 target보다 큰 값이 된다. end를 pivot에 1 뺀 값을 할당하여 '기존 start부터 새로운 end지점까지의 새로운 탐색을 해준다.
3. 만약 pivot이 가리키는 값이 target보다 작다면 pivot보다 작은 위치에 있는 배열의 값들은 당연히 target보다 작은 값이 된다. start를 pivot에 1 더한 값을 할당하여 '새로운 start부터 기존의 end지점까지의 새로운 탐색을 해준다.

초기 세팅을 해준 이후에 함수를 호출해주면 원하는데로 답을 반환해준다.

주의할 점

• pivot 계산식을 잘 고려하여 만들어야 한다. 만든 논리를 알고리즘으로 구현하기 위해서는 배열에 인덱스로 접근을 한다. 만들어지는 pivot이 어떠한 경우에도 배열의 모든 인덱스를 가리킬 수 있는지 살펴봐야 한다.
• 나의 실수 부분인데, 재귀함수의 종료 조건 (start > end)를 (start >= end)로 지정했을 때의 문제가 있었다. 위 구현된 알고리즘의 경우에는 start 값과 end 값이 같아지는 경우에도 탐색 작업이 진행되어줘야 했지만, 후자의 경우처럼 조건문을 작성하면 이 경우 종료가 되어버린다.