탐색

Simple Search

• 탐색중에선 제일 비효율적
• O(N)
• WorstCase : 찾는 수가 배열의 맨 마지막에 있음

🔽code

public class Simple {
    public int search(int[] dataArr, int findNum) {
        for (int i = 0; i < dataArr.length; i++) {
            if (dataArr[i] == findNum) {
                return i; // 해당 위치 반환
            }
        }
        return -1; // 찾는 값이 없으면 -1
    }
    public static void main(String[] args) {
        int[] dataArr = {6, 3, 7, 8, 2};
        Simple simple = new Simple();
        int index = simple.search(dataArr, 8);
        System.out.println(index);
    }
}

---

Binary Search

• up/down 게임을 생각해본다.
• 탐색 회마다 탐색 대상을 1/2을 줄인다.
• ✨정렬이 되어 있는 배열✨에서만 사용가능하다.
• O(logN)

• 핵심로직

1. 중간값찾기
2. 시작점 혹은 끝점 옮기기
3. 1~2 반복
4. 중간값과 대상값이 같으면 리턴

🔽code

public class Binary {
    public static void main(String[] args) {
        int [] nums = new int[] {1,2,3,4,5,6,7,8,9,10,11};
        int findNum = 2; // 찾아야 하는 값

        int idxHead = 0;
        int idxEnd = nums.length - 1;
        int findresult = 0;

        while (idxHead <= idxEnd) {
            // 중간값 찾기
            int midIdx = (idxHead + idxEnd) / 2;   
            int midValue = nums[midIdx];
            // 인덱스(시작점, 끝점) 옮기기
            if (midValue > findNum) {
                idxEnd = midIdx - 1 ;
            } else if (midValue < findNum) {
                idxHead = midIdx + 1;
            } else {
                findresult = nums[midIdx];
                break;
            }
        }
        // 같은지 비교
        if (findresult == findNum) {
            System.out.println("탐색성공");
        } else System.out.println("탐색실패");
    }
}

코딩 후기

• while문 작성시 조건을 주는 부분에서 idxHead == idxEnd 라고 설정함. -> idxHead <= idxEnd으로 정정
• int midIdx = (idxHead + idxEnd) / 2; 이 부분도 nums.length / 2로 설정했다가 nums는 변화하지 않으니 인덱스 옮길때 문제가 생겼었다.