[Algorithm 기초] 이진 탐색

 

이진 탐색 (Binary Search)

  - 정렬된 상태의 데이터에서 특정값을 빠르게 탐색하는 방법

  - 찾고자 하는 값과 데이터 중앙에 있는 값과 비교

  - 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색

  - 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색

 

  알고리즘 복잡도 : O(logn)

 

 

 

//이진탐색 사용예제01
//20240224 알고리즘 - 이진 탐색

public class binarySearch {
    //반복문 구조 버전
    public static int binarySearch(int arr[] , int target){
        int left = 0;
        int right = arr.length - 1;
        while (left <= right){
            int mid = (left + right) / 2;

            if (target == arr[mid]){
                return mid;
            }else if (target < arr[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }

    //재귀 호출 구조 버전
    public static int binarySearch2(int[] arr, int target, int left, int right){
        if(left > right){
            return -1;
        }

        int mid = (left + right) / 2;

        if (target == arr[mid]){
            return mid;
        }else if (target < arr[mid]){
            return binarySearch2(arr, target, left, mid - 1);
        }else{
            return binarySearch2(arr, target, mid + 1 , right);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60}; //정렬이 되어있어야 함

        System.out.println("Index : " + binarySearch(arr, 30));
        System.out.println();

        System.out.println("Index : " + binarySearch2(arr, 20, 0, arr.length -1));

    }
}

 

이진탐색 사용예제02

 

lower bound search

찾고자 하는 값보다 크거나 같은 것 중에서 가장 작은 값을 찾아주는 이분검색방법

 

upper bound search

찾고자 하는 값보다 큰 것 중에서 가장 작은 값을 찾아주는 이분검색방법

 

 

 

 

참고link

https://j-sik.tistory.com/21

[알고리즘] 이진 탐색(Binary Search) - 장점과 복잡도