📚 Algorithm Study - 2024-11-25

📝 학습 주제

• 알고리즘 이름: 이분탐색 (Binary Search)
• 분류: 탐색
• 주요 개념:
  • 정렬된 배열에서 특정 값을 찾거나 범위를 탐색할 때, 탐색 범위를 절반씩 줄이며 진행하는 효율적인 알고리즘.
• 장점:
  • 탐색 시간이 O(log N) 으로 빠르다.
  • 입력 데이터가 정렬되어 있다면 구현이 간단.
  • 큰 데이터에서 특정 값을 빠르게 탐색 가능.
• 단점:
  • 데이터가 정렬되어 있지 않으면 사용할 수 없음(정렬 필요).
  • 구현 과정에서 경계값 처리에 주의가 필요.

🧐 알고리즘 개념

• 정의:

  이분 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 효율적으로 찾기 위해 탐색 범위를 절반씩 줄여나가는 알고리즘이다. 일반적으로 반복문이나 재귀를 사용해 구현하며, 시간 복잡도가 O(log N)으로 매우 빠르다.

• 작동 방식:

  1. Step 1: 배열의 중간값(mid)을 계산합니다.
  2. Step 2: mid의 값과 찾고자 하는 값(target)을 비교합니다.
     • target == array[mid]: 값을 찾은 경우, 탐색 종료.
     • target < array[mid]: 탐색 범위를 중간값의 왼쪽 부분으로 축소.
     • target > array[mid]: 탐색 범위를 중간값의 오른쪽 부분으로 축소.
  3. Step 3: 탐색 범위가 없을 때까지(즉, left > right가 될 때까지) 위 과정을 반복합니다.
     • 값을 찾지 못한 경우, 탐색 실패로 종료. 또는 최소, 최대 인덱스값 반환

• 필요한 자료구조:

  • 배열/리스트: 정렬된 상태의 데이터가 필요.
  • 정렬: 탐색 전 데이터가 정렬되지 않았다면, 추가로 정렬 작업이 필요.

🔢 알고리즘 구현

구현

• 알고리즘 그림 설명

• 코드:

  package 이분탐색;
  
  public class 이분탐색구현 {
      static int[] arr;
  
      public static void main(String[] args) {
  
          arr = new int[5];
          for(int i = 0; i < arr.length; i++){
              arr[i] = i*2 + 1;
          }
          int i = binarySearch(0, arr.length - 1, 0);
          System.out.println(i);
  
      }
  
      public static int binarySearch(int start, int end, int key){
  
          int middleIndex = (end + start) /2;
          if(end < start){
              if(end < 0)
                  return 0;
              else
                  return arr.length;
          }
          
          if(arr[middleIndex] == key){
              return middleIndex;
          }
          if(arr[middleIndex] > key){
              if(start == end)
                  return middleIndex + 1;
              return binarySearch(start, middleIndex - 1, key);
          }
          if(arr[middleIndex] < key){
              if(start == end)
                  return middleIndex;
              return binarySearch(middleIndex + 1, end, key);
          }
  
          return -1;
      }
  }