탐색 알고리즘

순차 탐색

탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미한다.
데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법이다.

    public int solution(int[] list, int findNum) {
        for (int i = 0; i < list.length; i++) {
            if (list[i] == findNum) {
                return i;
            }
        }
        return -1;
    }

시간복잡도 : O(N)

이진 탐색

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

 int binarySearch1(int key, int low, int high) {
        int mid;

        if(low <= high) {
            mid = (low + high) / 2;

            if(key == arr[mid]) { // 탐색 성공 
                return mid;
            } else if(key < arr[mid]) {
                return binarySearch1(key ,low, mid-1); // 왼쪽 부분 탐색 
            } else {
                return binarySearch1(key, mid+1, high); // 오른쪽 부분 탐색 
            }
        }

        return -1; // 탐색 실패 
    }

시간복잡도 : O(logN)