이진 탐색

• 배열의 가운데 있는 항목을 비교하여 크면 오른쪽 부분을 검색하고, 작으면 왼쪽 부분을 검색하여서 검색부분을 점차 축소해가면서 값을 탐색하는 것
• 그렇기 때문에 데이터가 정렬된 상태에서 사용해야함
• 분할과 정복 기법 사용
• 시간 복잡도 : O(long(n))

구현

function binarySearch(array, target) {
	let left = 0
    let rigth = array.length -1

    
    while (left <= right) {
       let mid = Math.floor((left + right) /2)
    	if (array[mid] === target) {
        	return array[mid]
        }
      	else if (array[mid] > target) { // 찾는 값보다 중간점이 크다면, 값이 왼쪽에 있다!
        	right = mid -1 // 그래서 오른쪽 끝점을 중간점보다 하나 낮은 곳으로 이동
        }
      	else if (array[mid] < target) { //찾는 값보다 중간점이 작다면, 값이 오른쪽에 있으므로
        	left = mid +1 // 왼쪽 끝점을 중간점보다 하나 많은 곳으로 이동시켜서
        } //다시 탐색한다
    }
  return -1
}