반응형
블로그 이미지
개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 IT 프로젝트에서 사용되는 툴들에 대해 많은 분들과 정보를 공유하고 싶습니다.
솔웅

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

카테고리

Leetcode - 704. Binary Search - Easy

2022. 8. 22. 12:44 | Posted by 솔웅


반응형

지난 글에서 Big O에 대해 알아보면서 Binary Search에 대해 언급 했습니다.

이번에는 Binary Search에 대해 공부 해 보겠습니다.

문제는 지난번 문제와 거의 유사합니다.

입력값은 정렬된 배열과 target 값입니다.

출력값은 target이 배열의 몇번째에 있는지 입니다.

 

또 한가지 조건은 지난번 배웠던 Big O 표기법으로 표시 됐습니다. O(log n)

이것을 충족 시키려면 Binary Search를 해야 합니다.

루프 내에서 배열의 첫번째 값에서 마지막 값까지 하나 하나 살펴 보는 것은 O(n) 입니다.

O(log n) 은 배열의 중간 값을 가져 와서 타겟 값과 비교 합니다.

그리고 타겟 값이 더 크면 왼 쪽 반을 버리고 오른쪽 반만 놓 고 다시 이를 반복 합니다.

그러면 검색을 하는 step 을 줄여서 시간과 리소스 사용량을 줄일 수 있습니다.

어떻게 작동 되는지 알아보기 위해 7번째 줄에 print 문을 넣었습니다.

루프의 첫번째 스텝에서는 가운데 값이 9를 가져 옵니다. 타겟값 5보다 크니까 오른쪽을 버리고 왼쪽만 가져 옵니다.

그 다음 다시 가운데 값을 가져오는데 그 값은 0 입니다. 타깃이 크니까 왼쪽을 버립니다.

다음 단계는 가운데 값이 3이라서 다시 왼쪽을 버립니다.

그 다음 가운데 값은 5 이 고 이는 타깃 값과 같으니까 이 값을 리턴 합니다.

배열의 아이템은 10 개 인데 4번만에 정답을 찾아 냈습니다.

 

타깃값을 14를 해도 4번째 만에 정답을 찾아 냈습니다.

 

이렇게 19를 넣었을 때는 3번쨰 만에 그리고 20을 넣었을 때는 네번째 만에 찾아냈습니다.

 

배열에 없는 값을 넣어도 4번째 만에 정답을 찾아 냈습니다.

 

이렇듯 배열에 있는 아이템이 10 개가 있는데도 최대 4번의 스텝 만으로 정답을 알아 낼 수 있는 것은 바이너리 검색을 사용했기 때문입니다.

이것을 Big O 표기법에 따르면 O(log n)으로 표시합니다.

 

전체 소스 코드는 아래와 같습니다.

 

class Solution {

    public int search(int[] nums, int target) {

        int left = 0, right = nums.length-1;

        int mid;

        while (left <= right) {

            mid = left + (right - left) /2;

            if(nums[mid] == target) {

                return mid;   

            } else if(target > nums[mid]) {

                left = mid+1;

            } else {

                right = mid -1;

            }

        }

        return -1;

    }

}

반응형