[LeetCode] 704. Binary Search

문제 출처: https://leetcode.com/problems/binary-search/

Binary Search - LeetCode

문제

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어지면, nums안에서 target을 찾는 함수를 작성하라. 만약 target이 있다면, 인덱스를 반환하고, 없다면 -1을 반환하라.

 

반드시 O(log n)의 시간 복잡도를 따라야 한다.

예제

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Explanation: 9 exists in nums and its index is 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

Explanation: 2 does not exist in nums so return -1

풀이

문제 제목을 보면 어떤 알고리즘을 적용해야 하는지 알 수 있지만, 문제의 내용만을 보고 어떤 알고리즘을 적용해야 하는지 생각해보자.

 

문제 내용을 보면 알고리즘의 시간 복잡도가 O(log n) 이여야 한다는 점에 주목할 필요가 있다.

 

시간 복잡도의 제약조건이 없었다면, 순차 탐색을 통해서 O(n) 시간 내에 target을 찾는 알고리즘을 사용할 수 있겠지만, O(log n) 제약 조건으로 인해서 각 스텝마다 탐색 범위를 반으로 줄이는 방법에 대해 고민해야 한다.

 

이때 사용할 수 있는 게 바로 이진 탐색인 것이고, 이진 탐색을 하기 위해서는 배열이 정렬되어 있어야 한다는 조건이 붙는데 다행히도 배열이 오름차순으로 정렬되어 있다고 하니, 이 부분에 대해서는 고려하지 않고 바로 이진 탐색을 수행하면 된다.

 let left = 0, right = nums.length-1;
 while (left <= right) {
     const mid = low + Math.floor((right-low)/2));
    if (nums[mid] == target) { return mid; }
    else if (nums[mid] > target) { right = mid - 1; }
    else { left = mie + 1l }
 }

Github: 704.js

opwe37/Algorithm-Study