TIL - 알고리즘 : 이분 검색

def search(target, nums):
[1] nums.sort()
[2] n = len(nums)
[3] lt = 0
[4] rt = n-1

[5] while lt <= rt:
[6]     mid = (lt + rt)//2

[7]     if nums[mid] == target:
            return mid + 1
[8]     elif nums[mid] >= target:
            rt = mid - 1
[9]     else:
            lt = mid + 1

[1] 들어오는 숫자 리스트를 일단 순서대로 정렬한다.
[2] 들어온 숫자리스트의 갯수를 변수화한다.
[3] 왼쪽 끝값의 인덱스를 정의한다
[4] 오른쪽 끝값의 인덱스를 정의한다
[5] 오른쪽 끝값이 왼쪽끝값과 크거나 같아질 때 까지 while문을 돌린다.
[6] 왼쪽 끝값과 오른쪽 끝값의 몫을 구한다.
[7] 나온 몫(mid)이 내가 찾고자 하는 target값과 같으면 몫값(mid)를 리턴한다. 여기서 mid는 인덱스이다. 몇번째인지 알기위해서는 1을 더해야한다.
[8] 인덱스가 mid인 값이 target(목표하는값)보다 크거나 같으면 목표하는 값이 미드 값보다 인덱스상 mid값보다 왼쪽에 있다는 뜻이다. 그래서 오른쪽 끝값(rt)를 mid - 1로 설정해준다. 즉, 오른쪽 끝값의 범위가 줄어들었음을 의미한다. 여기서 1을 빼주는 이유는 1도 아니었음이 >= 비교 연산자로 증명되었기 때문이다.
[9] else절에는 target(목표값)값이 mid값보다 오른쪽에 있는 경우다. 즉, 왼쪽 끝값(lt)를 mid + 1로 한다.

이 과정은 lt == rt가 될 때 까지 반복된다. 그 범위안에서 값은 [7]에서 찾아져서 리턴될 것이다.