[Java] Chapter 6. Binary Search(이진 탐색)

✔️ Linear Search

• search는 indexOf, contains, remove 같은 곳에서 이미 구현되어 있음
  // 이진탐색 : Collections.binarySearch => Comparable이 구현되어 있어야 함, 순서대로 정렬되어 있어야 함

예제)

PracticeLinearSearch.java

package BinarySearch;

import java.util.*;

// search는 indexOf, contains, remove 같은 곳에서 이미 구현되어 있음
// 이진탐색 : Collections.binarySearch => Comparable이 구현되어 있어야 함, 순서대로 정렬되어 있어야 함

public class PracticeBinarySearch {
    <T extends Comparable> T binarySearch(List<T> data, T target) { // 입력받을 인자 : 리스트, 찾을 데이터
        int min = 0;
        int max = data.size();
        while(min < max) {
            int mid = (max-min) / 2 + min; // 리스트의 가운데 인덱스 값
            T m = data.get(mid);

            int c = m.compareTo(target); // m과 target 비교
            if(c == 0) return m; // 값을 찾았을 때
            if(c < 0) min = mid+1; // 위치 옮김
            else max = mid;
        }
        return null;
    }
    void test() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
        System.out.println(binarySearch(list, 4));
    }
}

Test.java

package BinarySearch;

import java.util.*;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;

class LinearSearchTest {
    @Test
    @DisplayName("정상 동작 테스트")
    void binarySearch_ok() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

        Integer found = new PracticeBinarySearch().binarySearch(list, 4);
        assertEquals(4, found);
    }

    @Test
    @DisplayName("비정상 동작 테스트")
    void binarySearch_not_ok() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

        Integer found = new PracticeBinarySearch().binarySearch(list, 4);
        assertNull(found);
    }
}

실행 결과

• 비정상 동작 테스트가 빨간 불이 뜨는 것은 테스트의 실행 결과가 정상이라는 것