UpperBound1 [Java]이진탐색 총 정리(상한upper bound, 하한lower bound, 중복 고려, while문 범위 설정,Arrays.binarySearch()메소드 등) 이진탐색 Binary Search : 정렬된 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 것 시간복잡도 : O(log N) 중복에 대해 고려하지 않은 경우 - 찾고자하는 key가 존재하는지만 알아내면 됨 - 메커니즘 1. 탐색 범위 내의 배열의 중간 인덱스를 구한다. 2. 중간 인덱스의 값과 key의 값을 비교한다. 3. 값이 중간 값보다 작다면 왼쪽 부분을, 크다면 오른쪽 부분을 탐색하고, 같다면 해당 인덱스를 반환하고 종료한다. - 주의! 자료형의 최댓값 넘지 말기 보통 mid = (start + end) / 2 라고 표현하지만, 만약에 start + end 가 자료형의 최댓값을 넘어선다면 자바에서는 Overflow 오류가 발생 -> mid = start + (end - start) / 2 로.. 2023. 5. 19. 이전 1 다음
