lower bound1 [알고리즘] 이분 탐색 - JAVA 이분 탐색이분탐색은 탐색할 대상이 정렬된 상태에서 사용한다. 데이터의 특정 값을 찾기 위해 대상을 둘로 나눠 절반씩 줄여나가는 원리이다. 대상을 반씩 줄이기 때문에 시간복잡도는 O(logN)이다. 주어진 데이터에서 중복되지 않은 값이 주어질 때, 데이터 내에 특정 값이 존재하는지 여부를 확인하는 방법으로 많이 사용한다. 동작 방식은 다음과 같다. 1. 배열의 중간 값을 가져온다. 2. 중간 값과 검색 값을 비교한다. - 중간 값이 검색 값과 같다면 종료한다. (mid = key) - 중간 값보다 검색 값이 크다면 중간 값 기준 오른쪽 구간을 탐색한다.(right = mid-1) - 중간 값보다 검색 값이 작다면 중간 값 기준 왼쪽 구간을 탐색한다.(left = mid+1) 3. 값을 찾거.. 2024. 5. 17. 이전 1 다음