[Concept/Algorithm] 이분/이진 탐색 (Binary Search)

• 이분 탐색 알고리즘은 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다.
  • 이분 탐색 알고리즘은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다.
• 변수 3개 시작, 끝, 중간 값(start, end, mid)을 사용하여 탐색합니다.
• 찾으려는 target과 중간 위치 값 mid를 반복 비교하여 원하는 데이터를 찾아가는 과정입니다.
• 시간복잡도는 단계마다 범위를 절반으로 줄여나가므로 O(logN) 입니다.
  • ex) 32개 데이터-> 16개 데이터-> 8개-> 4개
• 이분 탐색은 반복문과 재귀 호출 방식으로 구현할 수 있습니다.

public classBinary_Search {
    //재귀 호출 방식으로 구현
    private static intbinary_search_recur(inttarget,intstart,intend) {
        if(start > end)return-1;
            int mid = (start+end) / 2;//중간값
        if(target == mid)returnmid;
        // target이 중간값보다 큰 경우,오른쪽에서 search
        else if(target > mid)returnbinary_search_recur(target, mid+1, end);
        else returnbinary_search_recur(target, start, mid-1);
    }

    //반복문으로 구현
    private static intbinary_search_for(inttarget,intstart,intend) {
        while(start <= end) {
            int mid = (start+end) / 2;
            if(target == mid)returnmid;
            // target이 중간값보다 큰 경우,오른쪽에서 search
            else if(target > mid) start = mid+1;
            else end = mid-1;
       }
            return-1;
    }

    static int[]sortedArr= {1,3,5,7,8,10,20,35,99,100};
    public static void main(String[] args) {
            System.out.print("순환 호출(재귀) 이용한 이진탐색 : ");
            System.out.println(Binary_Search.binary_search_recur(5, 0,sortedArr.length-1));
            System.out.print("반복을 이용한 이진탐색 : ");
            System.out.println(Binary_Search.binary_search_for(5, 0,sortedArr.length - 1));
        }
}