포스팅 목적 효율적인 탐색 알고리즘 중 하나인 이진 탐색을 코드 구현을 중심으로 알아봅니다. 이진 탐색의 정의 이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다. 예를 들어 특정 범위에 있는 숫자를 맞추는 UP & DOWN 게임을 할 때를 생각해 보면 가장 안정적이고 빠르게 답을 찾는 방법은 가장 한 숫자 범위 내에 있는 수 중에서 중간에 있는 숫자를 찍어서 그 숫자보다 큰지 작은지에 따라 다음 숫자를 결정하는 것 입니다. 이것이 이진 탐색입니다. 이진 탐색의 장단점 이진 탐색의 장점은 높은 효율성 입니다. 한 번 탐색할때 마다 탐색의 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log N) 입니다. 앞의 정의에 나왔듯이 이진 탐색은 정렬되어 있는 배열에서만 사용할 ..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 이전에 풀었던 #153. Find Minimum in Rotated Sorted Array 문제와 비슷한데 Minimum 이 아닌 target 값을 찾는 문제입니다. 처음에는 이전 문제처럼 minimum 을 먼저 찾은 뒤 구간을 왼족 구간 ( nums[0] ~ nums[minIdx - 1] ) 과 오른쪽 구간 ( nums[minIdx] ~ nums[nums.length - 1] ) 으로 나누어 Binary Search 를 하려고 했었지만 Min 값 대신 target 값을 구하는 것으로 컨셉을 잡았습니다. 핵심은 rotate 된 정렬된 left side, right side 로 나누어서 target 과 nums[mid] 를 비교하면서..