[Array, Binary Search] Find First and Last Position of Element in Sorted Array

 

오름차순으로 정렬된 배열에 대해 target이 주어지면, 이 타겟이 위치한 index의 시작과 끝을 구하라는 문제

binary search 문제다.

 

여기서 주의할 부분은 target이 2개이상이므로, target=mid일때 리턴하지 않고 mid까지 포함하여 범위를 자른다는 것이다.

기존의 binary search를 이용하면 range중 하나만 찾아낼 것이기 때문이다.

따라서 가장 먼저 등장하는 res[ 0 ]과 가장 나중에 등장하는 res [ 1 ]을 각각 구한다

 

 

res[0]의 경우는 다음과 같은 과정을 거친다.

mid를 정하고 해당 로직처럼 범위를 좁혀나가면, r=mid, l=mid+1로 설정하므로

l이 해당 target의 첫번째 위치가 된다

 

res[1]의 경우는 다음과 같은 과정을 거친다.

mid를 정하고 해당 로직처럼 범위를 좁혀나가면, r=mid-1, l=mid로 설정하므로

r이 해당 target의 끝위치가 된다