[Leetcode] Binary Search

Binary Search
- 문제
- 풀이
마무리

이번 글에서 소개해드릴 문제는 leetcode에 있는 알고리즘 프로그램의 문제 중 하나인 이진 검색에 대한 문제를 소개해드리도록 하겠습니다.

Binary Search

이진 검색은 O(log N)의 시간 복작도로 문제를 해결 할 수 있는 알고리즘입니다. 일반적으로 배열에서 특정 값을 찾는데 필요한 시간은 O(N)인 것에 비해서 상당히 빠르게 정답을 찾을 수 있습니다.

하지만 이진검색을 수행하기 위해서는 주어지는 배열이 정렬이 되어 있어야 합니다. 이점을 참고해서 해당 문제를 소개하도록 하겠습니다.

문제

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.

풀이

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;

        while (start <= end) {
            // 중간 값 구하기
            mid = (start + end) / 2;
            if (target == nums[mid]) {
                return mid;
            }else if (nums[mid] < target) {
                // start 지점 수정
                start = mid + 1;
            }else if (target < nums[mid]) {
                // end 지점 수정
                end = mid - 1;
            }
        }
        return - 1;
    }
}

오랜만에 문제를 풀다보니, 재귀 형태의 바이너리 서치를 구현하려고 시도했다가 다시 반복문 사용해서 문제를 해결했습니다.

마무리

알고리즘 풀이 능력에 대한 감이 많이 죽어 leetcode를 통해서 다시 한번 감을 살리려고 노력하고 있습니다. 뭐든지 기본이 중요한 법인데 기본기를 잊어간다는 느낌이 들어 다시 알고리즘 풀이 능력 향상에 힘을 쏟으려고 합니다.

읽어주셔서 감사합니다.

#binary search,
#leet code,
#능력 회복하기,
#알고리즘,
#이진 검색

글이 도움이 되셨다면, 커피 한 잔만 사주세요!

Comments

Copied to clipboard

[Leetcode] Binary Search

Table of Contents

Binary Search

문제

풀이

마무리