[Java] Binary Search 코드

 

leetcode.com/problems/longest-increasing-subsequence/

리트코드에서 LIS 문제를 보는데 궁금해왔던.. Arrays.binarySearch()함수 구현 부분을 발견해 기록 남깁니다.

 

아래의 코드에서 Arrays.binarySearch(dp, 0, len, num)코드는 

배열 dp에서 범위 [0, len)까지 봤을 때, 즉 0부터 len-1까지 범위를 확인했을 때 num값이 있는지를 찾는 함수입니다.

만약 num 값이 없다면 num이 들어가야 할 위치는 return하는데 이 경우 음수 index를 리턴합니다.

음수값인 경우 i = -(i+1)과 같은 공식을 통해 위치를 알아낼 수 있습니다.

(왜 음수를 이런 식으로 리턴하냐면.. 0과 양수의 리턴값은 num을 찾았을 때 리턴해야 하는 값이기 때문에 중복을 피하기 위함)

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}

 

Arrays.binarySearch()함수는 아래와 같이 대략.. 변형할 수 있습니다.

아래의 코드에서 binarySearch코드 부분은.. 찾는 값을 못찾는 경우 음수를 리턴하도록 되어있지 않지만 내부 구조는 동일해보입니다.

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        
        for(int x: nums){
            int i=0, j=len;
            while(i!=j){
                int m = (i+j)/2;
                if(dp[m] < x){
                    i = m+1;
                }else{
                    j = m;
                }
                
            }
            dp[i] = x;
            if(i == len){
                len++;
            }
            
        }
        
        return len;
    }
}