이분탐색(Binary Search) upper_bound, under_bound의 구현

장준표·2020년 3월 4일
0

알고리즘

목록 보기
1/1

이분탐색

binary search는 탐색 방법중의 기초라고 할 수있을 정도로 쉽게 생각 할 수있고 거의 왠만한 개발하는 사람이라면 알고 있을 거라 생각하는데, 구현하려고 하면 조금 까다로운 부분이 있다.
이걸 글로 쓰게된 이유는 가끔씩 문제를 풀다보면 이분탐색 문제가 나오는데,
만족하는 특정 값 중에서 최소를 구하시오(under_bound), 최대를 구하시오(upper_bound)같은 형식으로 구해야하는 경우가 존재하는데 매번 풀때마다 헷갈린다.
따라서 정리를 해놓으려고 글을 작성한다.

기본적인 이분 탐색의 특징 (정렬되있어야하고, O(logN),,)은 가볍게 생략..

둘 다 key값이 존재하지 않는 경우 key값보다 큰 값 중 가장 작은 값을 반환한다.
즉, 존재하는 key값이 여러개일 경우 사용된다고 생각하면 된다.

upper_bound

  • upper_bound라는 것은 만족하는 key 값을 초과하는 것가장 작은 것의 index를 반환한다.(즉 key 보다 첫번째로 큰값)
  • key 값이 존재 하지 않으면 key보다 첫번째로 큰 값을 반환
		
        // int target_val; <- target값
        // int arr[N]; (오름차순으로 정렬되어있음)
    	int l =0; 
       	int r = MAX_LENGTH-1; // index
        // l가 r랑 같아질때 까지
        while(l < r){
            int mid = (l+r)/2;
            if (arr[mid] <= target_val)
                l = mid+1; 
            else
                r = mid;
        }
       	return l;
        

여기서 l을 반환하게 되는데 , 마지막에 l==r이 되면서 나오게 되는데,
index l에 있는 값은 key보다 첫번째로 큰 값을 나타낸다.

under_bound

  • under_bound라는 것은 만족하는 key 값 중 가장 작은것을 반환(가장 작은 index)
  • key 값이 존재 하지 않으면 key보다 큰 가장 작은 정수를 반환
		
        // int target_val; <- target값
        // int arr[N]; (오름차순으로 정렬되어있음)
    	int l =0; 
       	int r = MAX_LENGTH-1; // index
        // l가 r랑 같아질때 까지
        while(l < r){
            int mid = (l+r)/2;
            if (arr[mid] < target_![](https://velog.velcdn.com/images%2Fchangjunpyo%2Fpost%2Fd9bdfcee-1e45-4209-87eb-9ee2bcd9e84b%2Fharley-davidson-eeTJKC_wz34-unsplash.jpg)val) <= 여기 부분의 =만 바뀜
                l = mid+1;
            else
                r = mid;
        }
       	return l;
        

여기서 l을 반환하게 되는데 , 마지막에 l==r이 되면서 나오게 되는데,
index l에 있는 값은 key값보다 큰것 중 가장 작은 값의 index 가리키고 있다. 만약 없다면 key값보다 작은 것중에 하나 더 큰 것 이므로 key값보다 큰 가장 작은값.

0개의 댓글