[LeetCode] 35. Binary Search(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

Binary Search - LeetCode

[문제 설명]

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 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

[입출력 예]

Example 1:

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

Example 2:

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

[문제 풀이]

오름 차순으로 정렬되어 있는 배열이 주어지면 배열에서 target에 해당하는 값이 존재하면 해당 위치를 리턴하면 되고
값이 존재하지 않으면 -1을 리턴하면 되는 문제다.

내가 작성한 알고리즘을 요약하자면

lower_bound 함수를 사용하여 target의 위치를 찾는다.

☑ 찾고자 하는 값이 배열에 있다면 해당 위치를 리턴한다.

☑ 찾고자 하는 값이 없다면 해당 값보다 큰 가장 작은 위치를 리턴한다.
☑ 위치를 알고 배열의 인덱스에 접근하기 위해서는 lower_bound 한 결과에 배열의 첫번째 시작 주소를 빼면 알 수 있다.

하지만! 찾은 위치가 0보다 작거나 배열의 사이즈와 같거나 큰 경우가 있을 수 있다.
예를 들어 배열이 -3, 5, 10 있고 13의 값을 찾으려고 한다.
배열에는 13이 존재하지 않기 때문에 13보다 큰 가장 작은 위치인 인덱스 3을 리턴한다.
하지만 배열은 인덱스 2까지 존재하고 인덱스 3에는 접근할 수 없기 때문에 -1을 리턴하면 된다.

[최종 코드]

[GitHub]

GitHub - SmallPeanutPark/LeetCode: LeetCode for Coding Test

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int location = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if(location < 0 || location >= nums.size()) {
            return -1;
        } else {
            if(nums[location] == target) {
                return location;
            } else {
                return -1;
            }
        }
    }
};