[알고리즘] 이진탐색 Binary Search - Java

 

이진탐색(Binary Search)에 대해 어느정도 공부했지만,

 

아래의 경우에 쓰는 정도로 인식하고 있었다.

 

** 순서대로 정렬이 되어있을때,

1) 정답의 후보군이 있을때, 가장 빨리 찾는 방법

2) LowerBound 및 UpperBound 찾는 방법

3) 어느 경계를 찾는 방법

 

다만 아래 문제를 풀다가 좀 더 광범위하게 사용할 수 있는것 같아 정리를 하려고 한다.

- 프로그래머스 > 입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

> 위에서는 l과 r을 최소, 최대 걸리는 시간으로 잡아 시작했고,  Target (n명) 의 최적화 시간을 구해내었다.

 

 

ㅇ Binary Search 1 - while문으로

    Binary Search 2 - 재귀형식으로

  =>   l과 r 비교시 등호가 들어가고, l과 r을 mid-1, mid +1 로 해서 무한 루프에 걸리지않게 하는걸 기억하자.

public class test {

    static int binarySearch1(int target, int[] arr){
        int mid;
        int l = 0;
        int r = arr.length-1;
        while(l<=r){
             mid = (l+r)/2;
            if(target == arr[mid]){
               return mid;
            } else if (target < arr[mid]){
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        return -1;
    }

    static int binarySearch2(int target,int l,int r, int[] arr){
	if(l<=r){
          int mid = (l+r)/2;
          if(target == arr[mid]){
              return mid;
          } else if (target < arr[mid]){
              return binarySearch2(target,l,mid-1,arr);
          } else {
              return binarySearch2(target,mid+1,r,arr);
          }
       }
       return -1;
    }


    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

        int findIdx1 = binarySearch1(10, arr);
        int findIdx2 = binarySearch2(10,0,arr.length-1,arr);

        System.out.println("findIdx1 = " + findIdx1);
        System.out.println("findIdx2 = " + findIdx2);
    }
}