5.이진탐색 알고리즘

• 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

• 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  - 이진 탐색은 시작점, 끝점, 중간점을 이용해 탐색범위를 설정

• 시간 복잡도
• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례
• 이진탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장

재귀적 구현
function binarySearch(array, target, start, end) {
  	mid = (start + end) / 2
	if (start > end) {
    	return Null
    }
  	else if (array[mid] == target) {
    	return mid         
    }
    else if (array[mid] > target) {
    	return binarySearch(array, target, start, mid -1)
    }
  return binary_search (array, target, mid+ 1, end)
}

반복문 구현
function binarySearch(array, target, start, end) {
	while (start <= end) {
    	mid = (start + end) / 2
     if (array[mid] === target) {
     	return mid
     }
     else if (array[mid] > target {
             end = mid - 1 // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 
      }
     start = mid + 1 //중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    }
  return None
}

파라메트릭 서치(Parametric Search)

최적화 문제를 결정 문제로 바꾸어 해결하는 기법
-특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
-이진 탐색을 이용해서 해결할 수 있음

<문제> 떡볶이 떡 만들기

절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단
높이가 H보다 긴 떡은 H위의 부분이 잘릴 것, 낮은 떡은 잘리지않음
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램 작성

• 문제 해결 아이디어
• 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 됨
• 현재 이 높이로 자르면 조건을 만족할 수 있는가? 조건의 만족 여부에 따라서 탐색범위를 좁혀서 해결할 수 있음

function riceCakeLength(Number, M, array) {
	start = 0
  	end = Math.max(array)
 	result = 0
  
  	while (start <= end) {
    	total = 0
      mid = (start + end) / 2
      for (let i = 0; i < array.length; i++) {
      	if ( array[i] > mid) {
        	total += array[i] - mid
        }
       if (total < m) {
       	end = mid -1
       }
      result = mid
        start = mid + 1
      }
    }
  return result
}

<문제> 정렬된 배열에서 특정 수의 개수 구하기

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어있음
이때 이 수열에서 x가 등장하는 횟수를 계산
시간복잡도 O(logN)으로 알고리즘 설계할 것

• 문제 해결 아이디어
  데이터가 정렬되어있기 떄문에 이진탐색 수행할 수 있음
  특정 값이 존재하는 첫번째 위치와 마지막 위치를 찾아서 위치 차이를 계산해 문제를 해결할 수 있음