[알고리즘] 이진 검색 (Binary search) - 자바 Java

📍 검색이란?
- 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
- 목적하는 탐색 키(자료를 구별하여 인식할 수 있는 키)를 가진 항목을 찾는 것

[ 이진 검색이란? ]

: 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하여 검색을 진행하는 방법
- 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써, 검색 범위를 반으로 감소시켜 보다 빠르게 검색 가능
- 이진 검색을 위해서는 자료가 반드시 정렬된 상태여야 함

[ 검색 과정 ]

- 자료의 중앙에 있는 원소를 고르고 찾고자 하는 목표 값을 비교
- 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해 새로 검색을 수행, 반대는 오른쪽 반에 대해 검색 수행
- 찾고자 하는 값을 찾을 때까지 반복

[ 코드 예시 - 자바 Java ]

package search;

public class BinarySerach {
  
  public static void main(String[] args) {
  
    int[] arr = {1, 3, 5, 7, 9};
    
    System.out.println(binarySearch1(arr, 2));
    System.out.println(binarySearch2(arr, 0, 4, 3));
  }
  
  // 1. 조건문 통한 구현.
  static boolean binarySearch1(int[] arr, int key) {
    int start = 0;
    int end = arr.length-1;
    
    while(start<=end) {
      int mid = (start+end)/2;
      if(arr[mid] == key) return true;
      else if(arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return false;
      }
  // 2. 재귀함수 통한 구현.
  static boolean binarySearch2(int[] arr, int lo, int hi, int key) {
    if(lo > hi) return false;
    int mid = (lo + hi) / 2;
    
    if (arr[mid] == key) return true;
    else if(arr[mid] < key) {
      return binarySearch2(arr, mid+1, hi, key);
    } else {
      return binarySearch2(arr, lo, mid-1, key);
    }
  }

}