배열에서 검색

배열을 검새갛는 방법은 여러가지가 있지만 지금은 가장 간단한 방법에 중점을 둘것입니다.

선형 검색(Linear Search)

---

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키을 갖는 요소를 만날 때 까지 맨앞부터 순서대로 요소를 검색하면 되는데 이것이 선형 검색 또는 순차 검색 알고리즘 입니다. 최악의 경우 선형 검색은 전체 배열을 검사하게 된다.

따라서 선형 탐색의 시간 복잡도는 O(n) 이 걸린다

public static int linearSearch(int arr[], int x) {
    int n = arr.length;

    //순차적으로 arr[]각 요소와 x를 하나씩 비교  
    for (int i = 0; i < n; i++) {
		// 일치할경우 인덱스 반환
        if(arr[i]==x) {
            return i;
        }
    }
   //일치하지 않을 경우 -1 반환
    return -1;
}

 

 

 

이진 탐색(Binary Search)

---

배열의 요소가 정렬된 경우 이진 검색을 사용할 수 있다. 이진 탐색은 배열의 중간 요소를 반복적으로 확인하여 찾고 있는 요소가 왼쪽인지 오른쪽인지 여부를 결정한다. 매번 검색할 때 마다 검색해야 하는 요소 수가 절반으로 줄어들어 선형 검색보다 훨씬 빠르게 이진 검색을 수행할 수 있다.

그러나 이전 검색의 단점은 데이터가 정렬된 경우에만 작동된다는 것이다. 단일 검색만 수행하면 되는 경우에는 선형 검색보다 정렬 시간이 더 오래 걸리기 때문에 선형 검색만 하는 것이 더 빠르다.

public static int binarySearch(int[] arr, int x) {
    int left = 0;
    int right = arr.length -1;

    //왼쪽위치가 오른쪽 위치보다 커질때까지 반복
    while (left <= right) {
        //중간요소 위치 계산
        int mid = left + (right-left)/2;

        // 중간 요소와 일치하면 중간 인덱스를 반환
        if(arr[mid] == x) {
            return mid;
        }

        // x가 중간 요소보다 클 경우
        if(arr[mid] < x) {
            // 중간 요소 다음의 오른쪽 절반 하위 배열에만 놓고, 오른쪽 절반을 반복
            // 왼쪽 위치 재조정
            left = mid + 1;

        // x가 중간 요소 보다 작은 경우
        }else {
            // 왼쪽 절반 하위 배열만 놓고, 왼쪽 절반에 반복
            // 오른쪽 위치 재조정
            right = mid - 1;
        }
    }
    //찾을수 없을 경우 -1 반환
    return -1;
}

	좋은 시간 복잡도	평균 시간 복잡도	최악의 시간복잡도
Linear Search	O(1)	O(n)	O(n)
Binary Search	O(1)	O(n)	O(n)