알고리즘: binarySearch

문제

Write a function called binarySearch which accepts a sorted array and a value and returns the index at which the value exists. Otherwise, return -1.

예시

binarySearch([1,2,3,4,5],2) // 1
binarySearch([1,2,3,4,5],3) // 2
binarySearch([1,2,3,4,5],5) // 4
binarySearch([1,2,3,4,5],6) // -1
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 10) // 2
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 95) // 16
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 100) // -1

풀이

function binarySearch(arr, val){
	  let start = 0;
	  let end = arr.length-1;
	  let middle = Math.floor((start+end)/2)
	  
	  while(arr[middle] !== val && start<=end) {
	    if(val < arr[middle]) end = middle -1;
	       else start = middle + 1;
	       middle = Math.floor((start+end)/2)
	  }
	  return arr[middle] === val ? middle : -1
	}

포인트

• start와 end 포인트를 잡는 것
• for문 대신 while문을 돌리는 것 => 특정한 조건(arr[middle]!==val)이 만족되는 한 계속 돌리는 방법으로 while문이 적절함
• while문이 한 번씩 돌 때마다 "window"의 start와 end를 다시 설정해 주는 것
• val값이 arr안에 없을 경우, start가 end를 넘어서까지 while문이 계속 돌 수 있으므로 start <= end 일 때까지 while문이 돌도록 조건 추가하기