오늘의 알고리즘 문제

위코드 Chill기 동기들과 알고리즘 30일 challenge!

문제는 여기서 발췌!

오늘의 문제

주어진 nums 내에 target과 일치하는 수의 index를 return하는 문제로 만약에 target과 일치하는 수가 없을 경우 -1을 return

• 마지막의 O(log n)에 맞게 runtime을 구성하라는 조건에
  Binary search로 방향을 잡았다.

Binary Tree는 무엇일까?

정렬되어 제시된 내용 속에서 검열을 최대한으로 줄이는 방식으로
전체 Array에서 반을 잘라 그 중간 숫자가 target과 일치하는지를 1차적으로 검열

일치하지 않을 경우, 숫자가 target보다 큰지 작은지를 구별하여 다시 그 반에 이등분을 하고 또 그 이등분에 이등분을 하는 과정을 통해 검열하는 횟수를 줄이는 방식이다.

Binary Search를 통해 문제를 푼 모습

하지만 이건 틀린 풀이었으니!!!!!!!!!

주어진 배열이 정렬에 맞지 않아도 해당 인덱스를 구해야 하는 형식이었다.

For Loop를 통해 문제를 푼 모습

이렇게 하나씩 검열하여 문제를 풀어야 정답이라고 나오는데

저 O(log n) 조건은 왜 붙어있는 것일까?

다른 문제 풀이법이 있는 것을까?

indexOf 함수를 통해 푼 모습

관련해 얘기를 나누다가 동기분의 방법을 통해 더 간단한 방법도 찾았다!

정답!

배열에서 최소값을 찾아 그 값의 인덱스를 root로 정하고 거기서부터 수와 target을 비교해서 시작점이나 끝점을 변경하며 찾아보는 방법