Binary Search의 while loop 종료 조건 low < high, low <= high, low + 1 < high의 차이

이분 탐색을 진행할 때 while 문을 종료시키는 여러가지 방법 중 아래의 3가지를 언제 어떤 것을 사용해야 할지를 알아본다.

 

세 조건의 차이점

기본적으로 어떤 조건으로 while 문을 종료시키든 차이가 없다. 하지만 본인이 어떤 식으로 구현하고 싶은지, 어떤 내용을 구현하고 싶은지에 따라 달라지므로 세세한 내용을 알아둘 필요가 있다.

 

mid = (low + high) >>> 1로 가정한다.

 

low < high

low는 inclusive, high는 exclusive. low == high가 됐을때 while 문이 종료된다.

high를 exclusive하므로 high = mid, low = mid + 1로 업데이트한다.

 

loop가 끝난 low 혹은 high를 가지고 로직을 이어나가고 싶을때 low < high를 사용한다.

찾고자 하는 값이 무엇인지 모를 때, 존재하는지 모를 때 사용한다.

e.g. loop 내의 최소값을 찾아라.

 

class Solution {
    public int findMin(int[] nums) {
        var low = 0; var high = nums.length - 1;
        
        //low == high에 탈출
        while (low < high) {
            var mid = (high + low) >>> 1;
            
            if (nums[mid] > nums[high]) low = mid + 1;
            else high = mid;
        }
        //최소값은 언제나 low index에 존재
        return nums[low];
    }
}

 

low <= high

low와 high 둘 다 inclusive. 일반적으로 while문 내부에서 if condition을 걸어 target을 찾을때 while 문이 종료된다.

high = mid - 1, low = mid + 1로 업데이트한다.

 

early termination이 가능한 low <= high가 low < high보다 빠를 것같지만 매 loop마다 if condition을 체크해야하는 low <= high가 일반적으로 가장 마지막에 한번만 체크하는 low < high보다 느리다. #

 

target이 존재하지 않을 경우 infinite loop에 빠질 수 있다.

 

loop 내에 target이 존재하는 것을 알때 low <= high를 사용한다.

if (target == mid) 조건도 따라와야 한다.

e.g. 특정 target이 존재하는 것을 알고 있을때 target의 index를 return.

 

 

low + 1 < high

low와 high 둘 다 exclusive. 

high = mid, low = mid로 업데이트한다.

 

low와 high가 adjacent할때 탈출하므로 low <= high에서 target이 존재하지 않을때 발생하는 infinite loop를 방지할 수 있다.

adjacent 경우에 탈출하므로 while loop가 끝나고나서 low와 high 두 인덱스에 대한 validation이 필요하다. #

 

class Solution {
    public int findMin(int[] nums) {
        var low = 0; var high = nums.length - 1;
        
        //low와 high가 adjacent시 탈출
        while (low + 1< high) {
            var mid = (high + low) >>> 1;
            
            if (nums[mid] > nums[high]) low = mid;
            else high = mid;
        }
        //두 값 중 최소값을 찾아서 return
        return Math.min(nums[low], nums[high]);
    }
}

 

레퍼런스

https://stackoverflow.com/questions/35613574/when-to-use-in-binary-search-condition

When to use "=" in binary search condition?

https://stackoverflow.com/questions/44231413/binary-search-using-start-end-vs-using-start-end

Binary Search using start < end vs. using start <= end

https://stackoverflow.com/questions/30928268/binary-search-condition/30928332#30928332

Binary search condition