質問:
数値nums配列の昇順と検索するtargetをパラメータとすると、
targetはいくつかのindexです.戻ってください.
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に戻ってください.
nums配列の要素に重複値はありません

問題解決

今回はバイナリ探索を学び、それを利用して解決します.

の昇順なので、まず中央値

をチェック
検索する数字がもっと大きい場合は、リストの右側に表示されます.逆方向に検索する数値が小さい場合は、リストの左側に表示されます.

リストを2つの部分に分ける、中央値

をターゲットリストの他端に確認し続ける.

ならそこでさらに半分割って右に移動…

このように探し続けて、目標を見つけたら帰ります!最後まで蹴れない場合-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)wherenはlen(list)です.

ですが、ずっとターゲットリストを半分に分けて探していたので、リストの半分の半分の...このように

は数学的にlog 2(n)なので、次のグラフのように早くターゲットの原理を見つけることができます!

の最後の部分🌈