이것저것 코딩하는 블로그

0. lower bound / upper bound란? 만약 내가 찾는 값(타겟)이 배열에 여러 개 있다면, 이진 탐색을 실행했을 때 어떤 위치가 나오게 될 지 모른다. 따라서 우리는 이런 경우를 방지하고자 lower bound, upper bound를 사용한다. lower bound란 타겟 이상의 값이 최초로 나오는 위치를 의미한다. upper bound란 타겟을 초과하는 값이 최초로 나오는 위치를 의미한다. 따라서 타겟은 lower bound와 upper bound 사이에 있을 것이므로, 타겟이 여러 개일 때 타겟의 갯수를 세는 것이 가능해진다. 만약 타겟이 배열 내에 없다면, upper bound - lower bound = 0이 될 것이다. 타겟 이상의 값과 타겟 초과의 값이 동일하다는 것은 타겟..

0. Binary Search (이진 탐색) 이란? 업-다운 게임을 생각해보자 (술을 많이 안 먹으면 모를 수도 있다..이 경우엔 검색해보자). 범위 내에서 특정 숫자를 말하면 업, 다운을 이야기하며 맞추면 당연히 모두 읊는 것보다 시간이 덜 소요될 것이다. 이진 탐색과 이 개념은 정확히 일치한다. 배열이 정렬되었다고 가정하자. 이진 탐색은 정렬된 배열에 대해서만 가능하다. 정렬된 배열의 가운데에서 업, 다운 중 하나를 선택하면 왼쪽 혹은 오른쪽으로 이동할 것이다. 이제 이동한 배열의 가운데를 다시 기준으로 업, 다운을 선택하면, 범위가 계속 좁아지며 결국 원하는 대상을 찾을 수 있을 것이다. 만약 원하는 대상이 없다면, 배열의 원소가 하나만 남았을 때도 원하는 대상이 아닐 것이고, 이 때는 찾을 수 없..