이진 탐색(Binary Search)

탐색할 크기를 절반씩 줄여나가며 값을 탐색해나가는 알고리즘

 

1. 전체 배열의 중간값을 기준으로 앞 뒤를 나눈다.

2. 탐색하는 값이 중간값보다 크다면 뒤의 배열에서 다시 중간값을 나누고 탐색

3. 탐색하는 값이 중간값보다 작다면 앞의 배열에서 다시 중간값을 나누고 탐색

 

시간복잡도

매번 절반씩 나눠가며 탐색하므로 O(logn)

 

공간복잡도

O(logn)

 

Code

반복문

class Main {
    public static void main(String[] args) {
      int[] data = {7,9,10,14,17,19,26};
      int idx = binarySearch(data, 14);
      System.out.println("idx " + idx);
    }

    public static int binarySearch(int[] data, int target) {
      int start = 0;
      int end = data.length - 1;
      int mid = (start + end) / 2;

      while (start < end) {
        System.out.println("start " + start + " end " + end + " mid " + mid);
        if (data[mid] == target) {
          return mid;
        }
        if (data[mid] > target) {
          end = mid;
        } else {
          start = mid + 1;
        }
        mid = (start + end) / 2;
      }
      return -1;
    }
}

/*
결과
idx 3
*/

 

재귀

class Main {
    public static void main(String[] args) {
      int[] data = {7,9,10,14,17,19,26};
      int idx = binarySearchWithRecursion(data2, 19, 0, data.length-1);
      System.out.println("recursionIdx " + idx);
    }

    public static int binarySearchWithRecursion(int[] data, int target, int start, int end) {
      if (start > end) {
        return -1;
      }

      int mid = (start + end) / 2;

      if (data[mid] == target) {
        return mid;
      }

      if (data[mid] > target) {
        return binarySearchWithRecursion(data, target, start, mid-1);
      } else {
        return binarySearchWithRecursion(data, target, mid+1, end);
      }
    }
}

/*
결과
recursionIdx 6
*/