leetCode (Two Sum II - Input array is sorted) - Array, Binary Search

문제

Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

 

Example 1:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1 Output: [1,2]

 

---

배경지식

이분탐색 - 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인 하는(O(N))  대신, 탐색 범위를 절반으로 줄여가며 찾는 방법

 

풀이방법

1. map을 사용해서 풀었음 O(N)

const twoSum = (numbers, target) => {
    let map = new Map();

    for (let i = 0; i < numbers.length; i++) {
        if (map.has(numbers[i])) return [map.get(numbers[i]), i + 1];
        else map.set(target - numbers[i], i + 1);
    };
};

 

2. 이분 탐색으로 풀었음 O(logN)

const twoSum = (numbers, target) => {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        let sum = numbers[left] + numbers[right];

        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
};