이진탐색 알고리즘

키워드

• 반씩 쪼개는 탐색
• 정렬 된후에 탐색
• 1억이면 30번 정도 탐색하면 됨

시간 복잡도

순차탐색이 O(N)이라면 이진탐색은 O(logN)이다.

그래서 언제 이진탐색을 풀어야 할까?

• 만약 범위가 억이 넘어가는게 존재할 경우
• 데이터 정렬 뒤에 다수의 쿼리를 날려야 할 경우

풀기1 : 원하는게 arr에 있니?

const binarySearch = (arr, target, start, end) => {
	//탐색 실패(값 없음)
  	if(start > end) return -1;
  	let mid = parseInt((start+end)/2);
  	//만약 찾았다면 현재 index return
  	if(arr[mid] === target) return mid;
  	//start target mid end
  	else if(arr[mid] > target) return binarySearch(arr, target, start, mid-1);
  	//start mid target end
  	else if(arr[mid] < target) return binarySearch(arr, target, mid+1, end);
}

풀기2: 정렬된 배열에서 특정 원소의 개수 구하기

추후에 세그먼트 트리와 같은 복잡한 알고리즘에서 활용됨

c나 python에서는 lowerBound(), upperBound()라는 함수를 사용해서 해결할 수 있지만, javascript는 직접 구현해야함

cont lowerBound = (arr, target, strat, end) => {
	while(start < end){
    	let mid = parseInt((start+end)/2);
      	if(arr[mid] >= target) end = mid;
      	else start = mid + 1;
    }
  	return end;
}

const upperBound = (arr,taret, start, end) => {
	while(start < end){
    	let mid = parseInt((start+end)/2);
      	//start target arr[mid] end
      	//start target mid mid mid mid arr[mid] end
      	if(arr[mid] > target) end = mid;
      	//start arr[mid] target1 target2 end => start: target1
      	//start target1 arr[mid] target2 end => start: target2
      	else start = mid + 1;
    }
  
  	return end;
}

풀기3: 파라메트릭 서치

다른 고급 알고리즘 문제랑도 연결됨

단조증가함수

• 단조 증가 함수란 x <= y 이면 f(x) <=f(y)인 함수를 의미합니다.
• 이진탐색 함수는 정렬된 배열을 다루기 때문에 단조 증가 함수입니다.

파라메트릭 서치

• 최적화 문제를 여러개의 결정문제로 바꾸어 해결하는 기법

  최적화 문제: 최댓값, 최솟값을 찾는것 저럼 특정한 조건을 만족하는 알맞은 값을 빠르게 찾는 문제

실제 문제

• 2512