[Javascript 코테 대비] 이진 탐색: Binary Search

Binary Search: 이진 탐색

재귀 함수로 구현한 이진 탐색

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

반복문으로 구현한 이진 탐색

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

실제 문제 풀이 시

• 코딩 테스트의 이진 탐색 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많다. 탐색 범위가 2,000만(2000,0000)을 넘어가면 이진 탐색으로 문제에 접근해봐야 한다.