시작하게 된 이유

리트코드 14일 알고리즘 부시기 코스라고 적혀있는 것을 시작한 이유는 최근 프로그래머스를 통해 자료구조 강의를 보고 있기 때문이다.

프로그래머스에서 1단계 문제를 모두 풀고 난 뒤 2단계를 하려던 와중 기본지식(자료구조, 알고리즘 개념)이 부족하여 강의를 이것저것 찾아 듣고있는 상태인데 그래도 유명하다는 리트코드 Easy레벨 문제도 풀어봐야 되지 않겠나.. 라는 생각으로 접했는데

생각보다 꽤 어렵다 ㅎㅅㅎ..

1. 704.Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

1
2
3
4
5

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

1
2
3
4
5

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 104 -104 < nums[i], target < 104 All the integers in nums are unique. nums is sorted in ascending order.

2. 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

const search = (nums, target) => {
  let low = 0;
  let high = nums.length - 1;
  let mid = 0;

  //종결 조건은 찾거나 미들이 0 일때임
  //계속 돌면서 리스트의 중간 값이 타겟보다 큰 경우
  // 리스트의 중간값이 타겟보다 작은 경우
  while (low <= high) {
    mid = Math.floor((low + high) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
};

search([-1, 0, 3, 5, 1, 9], 9);

3. 결론

간단하게 이중 for문을 돌려 o^n으로도 풀 수 있다 mid에 관한 방법은 처음에 Math.ceil로 접근했으나 Math.floor가 미세하게 더 빨랐다. 아무래도 테스트케이스의 차이인가 싶기도하다

끝!

참고

• [LeetCode - 704.Binary Search]](https://leetcode.com/problems/binary-search/)