불로구

시간초과를 해결하기 위해 이진탐색이 필요 한 문제이다. package 백준.문제1920; import java.util.Arrays; import java.util.Scanner; public class Main { public static int sol(int a[], int key) { int start = 0; int end = a.length - 1; int result = 0; do { int center = (start + end ) / 2; if(a[center] == key) { result = 1; break; }else if(a[center] < key) { start = center + 1; }else { end = center - 1; } }while(start

이진탐색 - 오름차순 or 내림차순으로 정렬되어있는 배열에서 검색하는 알고리즘 -> 7찾기 step 1) start center end 5 7 9 11 13 15 17 step 2) start center end 5 7 9 - 이진탐색을 시작(0), 중앙( (배열길이 - 1 / 2) ) , 끝( 배열길이 - 1)으로 나눈다. - 찾는 값이 중앙 값 보다 작다면 -> 시작(0), 끝( 중앙-1 ), 중앙 ( (배열길이 - 1 / 2) )가 되고 - 찾는 값이 중앙 값 보다 크다면 -> 시작(중앙+1) , 끝( 배열길이 -1 ), 중앙 (배열길이 -1/2)가 된다. 종료조건 - 1) 중앙값과 key가 일치 - 2) 검색 범위에서 찾지 못함 시간복잡도 - 반복마다 검색 범위가 반으로 줄어든다 - 평균 : lo..