이진 탐색 (Binary Search)

이진 탐색이란 정렬된 리스트에서 탐색하는 범위를 절반으로 줄여가면서 원하는 값을 탐색하는 방법이다. 탐색 범위를 절반으로 줄여가기 때문에 시간 복잡도는 O(logN)이다. 

아래 리스트에서 3을 탐색한다고 하면,

1. start 값은 1 end 값은 10이 된다. 그리고 mid 값은 5가 된다. 3이 5보다 작기 때문에 mid 값인 5를 기준으로 왼쪽에 있는 값들을 이용해서 이진 탐색을 반복한다.
2. start 값은 1 end 값은 4가 된다. 그리고 mid 값은 2가 된다. 3이 2보다 크기 때문에 mid 값인 2를 기준으로 오른쪽에 있는 값들을 이용해서 이진 탐색을 반복한다.
3. start 값은 3 end 값은 4가 된다. 그리고 mid 값은 3이 되고 찾고하는 값이기 때문에 탐색을 종료한다

이진 탐색을 구현하는 방법에는 재귀와 반복문이 있다. (javascript)

//재귀 호출
function binarySearch(arr, target, start, end){
  if(start > end){
  	return;
  }
  const mid = Math.floor((start + end) / 2);

  if(arr[mid] == target){
  	return mid;
  } else if (arr[mid] > target){
  	return binarySearch(arr, target, start, mid - 1);
  } else if (arr[mid] < target){
  	return binarySearch(arr, target, mid + 1, end);
  }
}

//반복문
function binarySearch(arr, target, start, end){
  while(start <= end){
    const mid = Math.floor((start + end) / 2);
    if(arr[mid] == target){
    	return mid;
    } else if(arr[mid] > target){
    	end = mid - 1;
    } else if(arr[mid] < target){
    	start = mid + 1;
    }
  }
  return -1; //발견 못했을 시에는 -1 을 return
}