문제 :
오름차순인 숫자 nums 배열과 찾아야할 target을 인자로 주면,
target이 몇 번째 index인지 return 해주세요.
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
설명: 찾지 못하면 -1로 return 해주세요.
nums 배열에 있는 요소는 서로 중복된 값이 없습니다

문제 접근 ⚙️

• 이번에는 이진탐색을 배워서 그걸 이용해서 풀어야한다.
• 오른차순이기 때문에 중앙의 값을 먼저 확인
• 찾으려는 숫자가 더 크다면, 리스트의 오른쪽에 있다는 뜻.
• 반대로 찾으려는 숫자가 더 작으면, 리스트의 왼쪽에 있다는 뜻.
• 경우를 두 개로 나누듯이, 리스트를 반으로 나누어서 찾으려는 타켓이 있는 쪽으로 계속 중앙값을 확인
• 클 경우, 거기서 또 반을 쪼개서 오른쪽으로 이동 ...
• 이렇게 계속 찾아서 타켓을 찾으면 리턴 ! 끝까지 못차으면 -1을 리턴

코드 구현 🖊️

def search(nums, target):

  pos1 = 0					#pos1은 처음 부분
  pos2 = len(nums) //2		#pos2는 중앙부분
  pos3 = len(nums) -1		#pos3은 끝부분

  while nums[pos2] != target: #타켓을 찾을때까지 무한 루프

    if nums[pos2] > target:	#타켓이 중앙값보다 작다면 끝부분을 땡겨오고
      
      pos3 = pos2 -1
      pos2 = (pos1 + pos3)//2

    else:					# 타켓이 중앙값보다 크다면 처음부분을 중앙부분으로 업데이트 
      pos1 = pos2 + 1		# 다시 중앙 포지션 지정
      pos2 = (pos1+pos3)//2

    if pos1 > pos3:			# 만약 이렇게 계속하다가 어느순간 list의 처음이 끝보다 커지는 경우가 발생하는데 이때는 못찾은 거니 -1을 반환하면 된당!
      return -1

  return pos2

시간 복잡도로 보자면 🤔

• 찾고자하는 타켓을 만약 선형 탐색으로 찾았다면 O(n) where n is the len(liist)가 된다.
• 하지만, 해당 타켓을 계속 리스트를 반으로 쪼개면서 찾아가기 때문에 리스트의 반의반의반의 ... 이런식으로
• 수학적으로는 log2(n)이 되기 때문에 아래의 그래프처럼 더 빠르게 타켓을 찾을 수 있는 원리인 것이다 !

끝 🌈