[NeetCode-LeetCode] Binary Search JAVA

반응형

728x90

[NeetCode-LeetCode] Binary Search - Easy

---

접근

• 이진 탐색

---

풀이

NeetCode의 문제들 중 grind75에서 풀었던 문제를 제외하고 난이도 순으로 풀다 보니 easy 문제에선 기초적인 알고리즘 구현 문제가 나와 다시 돌아보는 느낌으로 푸는 중이다. 이번 문제는 이진 탐색 구현 문제이다. 정말 이진 탐색에 대해서만 구현하는 문제로 target이 주어지고 배열에서 이진 탐색을 통해 target의 인덱스를 반환하면 된다. 정말 친절하게 배열도 미리 정렬된 상태로 주어진다. 

 

코드는 너무 간단하니 이진 탐색에 대해 다시 돌아보고 넘어가자면 이진 탐색은 O(logn)을 만족하는 탐색 방법으로 연산 한 번 수행마다 범위를 절반씩 줄여나가며 탐색을 진행하기 때문에 log의 n 시간 복잡도를 가지게 되는 것이다. 이진 탐색을 수행하기 위해서는 값 비교를 위해 요소들이 정렬된 상태여야 하며 시작과 끝 포인터를 사용해 범위를 줄여가게 된다.

 

탐색 방법으론 먼저 현재 시작과 끝 포인터의 중간 위치를 구한다. 구해진 중간 위치에 존재하는 요소와 target의 값을 비교해 target이 해당 요소보다 작다면 중간 요소를 기준으로 왼쪽을 다음번에 탐색하게 되고 target이 크다면 오른쪽을 탐색하게 된다. 

arr = [1, 2, 3, ... , 98, 99, 100] target = 71

시작 포인터 0 끝 포인터 99 -> 중간 = (0 + 99) / 2 = 49
arr[49] = 50 -> target 비교 = 71 > 50 -> target > arr[49]
target인 71은 50보다 크기 때문에 50보다 오른쪽에 위치하고 있음 -> 중간 값을 기준으로 오른쪽 탐색
시작 포인터 = 49 + 1 = 50 끝 포인터 = 99

target을 찾을 때 까지 반복

위와 같은 과정으로 target이 위치한 곳으로 범위를 줄여나가며 탐색을 진행하게 된다.

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

        while (start <= end) {
            int mid = (start + end) / 2;

            if (nums[mid] == target) {
                return mid;
            }

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

---

전체 코드

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

        while (start <= end) {
            int mid = (start + end) / 2;

            if (nums[mid] == target) {
                return mid;
            }

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