99클럽 코테 스터디 28일차 - 이진탐색

Missing Number

풀이

• 연속된 숫자 중 없는 수를 찾으면 된다
• n이 10의 4제곱까지 있으므로 이진탐색으로 수행
• 아이디어는 nums[i] != i

코드

   class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int low = 0;
        int high = nums.length-1;

        while(low <= high) {
            int mid = (low + high) / 2;

            if(nums[mid] == mid){
               low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
     }

정리