Binary Search

https://leetcode.com/problems/binary-search/description/

Binary Search - LeetCode

 

이진탐색 알고리즘을 알고있는지 체크하는 문제로 O(log n) 시간복잡도를 요구한다.
특이점으로는 존재하지 않는 값을 타겟으로 하는 문제가 존재하고 그럴경우 -1 값을 리턴해야 한다는 것이다.

이진 탐색을 위해 low, high 값을 설정하고 mid를 인덱스로 하여 값을 비교하고, 값에 따라 low, high 미드값을 변경하여 mid 인덱스로 타겟을 찾아가는 방식이다

class Solution {  
    public int search(int[] nums, int target) {  
        int len = nums.length;  
        int low = 0;  
        int high = len - 1;  
        int mid = (low + high) / 2;  
  
        // while 의 조건문을 통해 타겟에 도달했는지 확인  
        while(nums[mid] != target){  
            int cur = nums[mid];  
            if(cur > target){  
                // index 범위를 초과하거나, 답이 없거나를 체크  
                if(mid - 1 < 0 || nums[mid - 1] < target){  
                    mid = -1;  
                    break;  
                }  
                // 중간점 체크를 위해 값 비교를 통해, low - high 값 전환  
                high = mid - 1;  
  
            }else{  
                // index 범위를 초과하거나, 답이 없거나를 체크  
                if(mid + 1 >= nums.length || nums[mid + 1] > target){  
                    mid = -1;  
                    break;  
                }  
  
                // 중간점 체크를 위해 값 비교를 통해, low - high 값 전환  
                low = mid + 1;  
            }  
            // 변경된 low, high 값을 이용해 새로운 중간점 변경  
            mid = (high + low) / 2;  
        }  
  
        return mid;  
    }  
}

 

답이 없는 부분을 체크하기 위해, 바로 근처 값을 확인 하는 방식을 넣었다.

이 때 인덱스가 배열의 범위를 초과하는지 체크하지 않으면 배열의 범위를 초과하는 인덱스 값을 검사하여

오류를 발생 시킬 수 있다.

 

이진 탐색 문제를 풀 때는 항상 범위를 잘못 처리하거나,

인덱스 조정 시 실수하여 while문을 탈출하지 못하는 실수를 할 때가 많다.

다행히 해당 문제는 조건이 까다롭지 않고 기초적인 이진탐색을 요구하기에 이진탐색을 입문하기 좋은 문제였다.