binary search

상계/하계(Upper Bound/Lower Bound)? Lower Bound와 Upper Bound는 이진 탐색을 기반으로 하여 경곗값을 찾는 알고리즘이다. 이진 탐색을 기반으로 하기 때문에 당연히 데이터가 정렬되어 있어야 한다. 값을 찾을 때, 원하는 값이 없을 때 못찾았다는 신호(-1, false 등)를 반환하는 일반적인 이진 탐색과 달리 Upper Bound와 Lower Bound를 이용하면 찾고자 하는 값 또는 그 값의 초과값이 처음 나타나는 위치를 찾을 수 있다. 때문에 주로 특정 값을 어느 위치에 삽입해야 하는지 탐색할 때 많이 사용한다. 상계 (Upper Bound) Upper Bound는 찾고자 하는 값(target)보다 큰 값의 처음 위치를 반환한다. 구현 public class Upp..

이진 탐색(Binary Search)? 이진 탐색이란 데이터가 정렬되어 있는 상태에서 탐색 범위를 줄여나가며 특정한 값을 탐색하는 알고리즘으로, 탐색할 때마다 탐색 범위가 반으로 줄어들기 때문에 속도가 빠르다는 장점이 있다. 구현 코드 public class BinarySearch { public static void main(String[] args) { int[] array = {1, 3, 4, 6, 7, 9, 10, 11, 14, 16, 17, 20}; int target = 16; int left = 0; int right = array.length - 1; while (left right가 되므로 종료한다) 시간 복잡도 선형 탐색의 경우 O(n)이지만 이진 탐색의 경우 O(log n)이므로 대부..