이진탐색(Binary Search) 개념정리

 

 

 

 

이진탐색(Binary Search)

정렬된 배열 또는 리스트에서 원하는 값을 빠르게 찾아내는 탐색 알고리즘

 

순서

1. 탐색 대상의 중간 인덱스를 찾습니다.
2. 중간 값과 찾고자 하는 값을 비교합니다.
3. 만약 중간 값이 찾고자 하는 값과 일치하면 탐색을 종료합니다.
4. 만약 찾고자 하는 값이 중간 값보다 작다면, 왼쪽 부분을 탐색합니다.
5. 만약 찾고자 하는 값이 중간 값보다 크다면, 오른쪽 부분을 탐색합니다.
6. 이 과정을 반복하여 원하는 값을 찾을 때까지 계속합니다.

 

이진 탐색과 선형 탐색의 차이점

 

• 선형 탐색(Linear Search)
  배열 또는 리스트를 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾습니다.
  배열 또는 리스트가 정렬되어 있지 않아도 사용할 수 있습니다.
• 이진 탐색(Binary Search)
  정렬된 배열 또는 리스트를 반으로 나누어 탐색 범위를 좁혀가면서 원하는 값을 찾습니다.
  배열 또는 리스트가 정렬되어 있어야만 사용할 수 있습니다.

정렬여부	정렬되지 않은 배열/리스트	정렬된 배열/리스트
탐색속도	느림	빠름
탐색범위	처음부터 끝까지	중간값ㅇ르 기준으로 좌/우측 반 중 하나
구현방식	for/while 루프 사용	재귀함수 사용
시간복잡도	O(n)	O(log n)

 

 

 

 

시간복잡도

O(log n)

 

 

 

이진탐색 트리

 

 

예제코드

 

array[mid] 값과 구하고자 하는 key값을 비교

• key > mid :  구하고자 하는 값이 중간값보다 높다면 low를 mid +1로 만들어 줌 (왼쪽 반을 버림)
• key < mid : 구하고자하는 값이 중간값 보다 낮다면 high를 mid-1로 만들어 줌 (오른쪽 반을 버림)
• key == mid : 구하고자 하는 값을 찾음 중간값 리턴 

 

반복문으로 구현

 // 이진 탐색 함수
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 중간 인덱스 계산

            if (arr[mid] == target) {
                return mid; // 값을 찾은 경우 인덱스를 반환
            } else if (arr[mid] < target) {
                left = mid + 1; // 탐색 범위를 오른쪽으로 좁힘
            } else {
                right = mid - 1; // 탐색 범위를 왼쪽으로 좁힘
            }
        }

        return -1; // 값을 찾지 못한 경우 -1을 반환
    }

 

 

 

 

 

 

재귀로 구현

 public static int binarySearch(int[] arr, int left, int right, int target) {
        if (right >= left) {
            int mid = left + (right - left) / 2; // 중간 인덱스 계산

            // 값을 찾은 경우
            if (arr[mid] == target) {
                return mid;
            }

            // 값이 중간값보다 작은 경우, 왼쪽 부분을 탐색
            if (arr[mid] > target) {
                return binarySearch(arr, left, mid - 1, target);
            }

            // 값이 중간값보다 큰 경우, 오른쪽 부분을 탐색
            return binarySearch(arr, mid + 1, right, target);
        }

        // 값을 찾지 못한 경우
        return -1;
    }

 

 

 

https://minhamina.tistory.com/127