← 11주차 · 이분 탐색과 결정 알고리즘
쉬움이진탐색배열

이진 탐색

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어져요. target이 배열에 있으면 그 인덱스를, 없으면 -1을 반환해요.

시간 복잡도 O(log n)으로 풀어야 해요.

예시

예시 1
입력
nums = [-1, 0, 3, 5, 9, 12], target = 9
출력
4
설명
9는 인덱스 4에 있어요.
예시 2
입력
nums = [-1, 0, 3, 5, 9, 12], target = 2
출력
-1
설명
2는 배열에 없어요.

제한 사항

  • 1 ≤ nums.length ≤ 10,000
  • nums는 중복 없이 오름차순 정렬되어 있어요.
  • -10,000 ≤ nums[i], target ≤ 10,000
lo와 hi 포인터를 두고 mid = (lo + hi) >> 1 을 확인해요. nums[mid]가 target보다 작으면 lo = mid + 1, 크면 hi = mid - 1 이에요.
javascript
function search(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
이전 문제다음 큰 원소
다음 문제삽입 위치 찾기
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.