이진탐색

정렬된 배열에서 특정한 값을 찾는 알고리즘

시간 복잡도는 O(logN)

mid=(start+end)/2가 찾고있는 값이 될때까지 실행한다.

찾을 값 k > mid

• start=mid+1은 범위를 늘리는 것

찾을 값 k < mid

• end=mid-1은 범위를 줄이는 것

 

 

🐝 예제

// 배열에서 이동
int start=0;
int end=max_num-min_num;
int mid;        // 차이값
int answer=200;
while(start <= end){
	mid=(start+end)/2;
    boolean suc=false;      // 차이값 mid가 성립하는지
    for(int i=min_num; i<=max_num; i++){
    	if(i <= map[0][0] && map[0][0] <= i+mid){
        	boolean check=bfs(i, i+mid);
            visited=new boolean[n][n];      // 초기화
            if(check){
            	suc=true;
                break;
            }
        }
     }
     if(suc){
     	answer=min(answer, mid);
        end=mid-1;      // 줄어든다.
     }else{
        start=mid+1;       // 커진다.
     }
}

(0,0)에서 (n,n)에 가는 경로들 중에서 최대값-최소값이 최소를 찾아야 한다.

mid가 최대값-최소값

min_num은 배열에서 최소값, max_num은 배열에서 최대값

 

 

// '징검다리 건너기'문제 중에서
while(left <= right){
            int zero=0;
            mid=(left+right)/2;
            for(int stone : stones){
                if(stone-mid <= 0){	// 디딤돌이 0인 칸은 밟지 못한다.
                    zero+=1;
                }else{
                    zero=0;
                }
                if(zero >= k){
                    break;
                }
            }
            if(zero < k){
                left=mid+1;
            }else{
                right=mid-1;
                answer=mid;
            }
        }

zero는 한 번에 건너띈 디딤돌의 칸수

한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k

mid는 징검다리를 건널 수 있는 최대 인원

 

 

 

참고 👇

https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제