how to make Binary Search

• 아 인터넷 사수님의 과제를 아직 못풀어서 자지도 못하고 😢
  저는 원래 12시에 "전" 자고 7시에 일어나는 어른이였는데요...

  이진탐색

  정독
  

조건

• 정렬된 데이터
• 배열의 형태
• 특정값 찾기
• 배열 중간의 임의의 값(Y) 선택
• 비교군 X 와 대조
  • Y > X
    Y를 기준으로 우측 데이터를 재탐색
  • X < Y
    Y를 기준으로 좌측 데이터를 재탐색
  • 해당값을 찾을때 까지 반복

특징

• logN 빠른 시간복잡도

output 

• c 와 비교

#include<stdio.h>

int list[9] = {1,3,5,6,7,9,11,20,30};
int search_binary (int key, int low, int high){ int middle;
  //low와 high가 같아질때까지반복
  while(low<high) {
      middle = (low+high)/2;
      // 찾는 값이 중앙값과 일치시 중앙값 반환
      if (key == list[middle])
              return middle; 
      // 찾는값이 중앙값보다 작으면 왼쪽 탐색
      else if (key <list[middle]) 
              high=middle-1;
      //찾는값이 중앙값보다 크면 오른쪽 탐색
      else  
      		low = middle+1;
  }
  // 탐색실패시-1 반환
  return -1;
}
// 실행 함수
int main(void){
	int num =search_binary(1,0,8);
    printf("%d", num);
}

• 탐색 횟수 0, 1,2 늘어나면 탐색범위는 n, n/2,n/4로 절반씩 줄어든다
  

• 탐색범위를 더이상 줄일수 없음 = 1

• 탐색횟수 k , 탐색범위 n/2^k

  예2 2

	arr = []
for _ in range(N):
	arr.append(int(input()))
    
start = max(arr)
end = sum(arr)

while start <= end:
	mid = (start+end)//2
    now =mid
    cnt =1
    for i in arr:
    	if now <i:
        	now =mid
            cnt +=1
        now -=i
    if cnt > M:
    	start = mid +1
    else :	
    	end = mid -1 
        ans = mid															
print(ans)

비교

• O(N)은 단순 배열 순회