이진검색

 

package algorithm;

import java.util.Arrays;

public class BinarySearch {
    static int search(int n, String[] data, String target) {

        Arrays.sort(data); //오름차순 정렬

        int begin = 0;
        int end = n - 1;
        while (begin <= end) { //begin이 end보다 커지면 더이상 비교할 것이 없다는 뜻이다.
            int middle = (begin + end) / 2;
            int result = target.compareTo(data[middle]);
            //target > data[middle] 1
            //target == data[middle] 0
            //target < data[middle] -1

            if (result == 0) {
                return middle;
            } else if (result < 0) { //미들값이 타겟값보다 크면, end값을 middle -1로 바꿔준다.
                end = middle - 1;
            } else {
                begin = middle + 1; //미들값이 타겟값 보다 작으면, begin값을 middle+1로 바꿔준다.
            }

        }

        return -1;
    }


    public static void main(String[] args) {
        String [] array = {"A","b","C","D","E"};
        int n = array.length;
        String target = "b";


        int se = search(n,array,target);

        System.out.println(Arrays.toString(array));
        System.out.println("답은 " + se);


    }
}

시간복잡도

• 한 번 비교할때마다 남아 있는 데이터가 절반으로 줄어든다.
• 👉🏻 따라서 시간 복잡도는 O(log2n)이다.

 

 

✏️

숫자/문자 비교(ComareTo) 

 

기준값.CompareTo(비교값);

• 기준값 == 비교값
  • 0 반환

• 기준값 > 비교값
  • 1 반환

• 기준값<비교값
  • -1 반환

👉🏻크다(1), 같다(0), 작다(-1)

문자열 비교

String str = "abcd";

str.compareTo("abcd") //0 -> 같은 문자열 0 반환
str.compareTo("ab") //2
str.compareTo("c") //-2 

• 기준값의 앞자리부터 일치하는 문자열이 포함된경우

👉🏻기준 문자열길이 - 비교대상 문자열 길이 리턴한다.

• 비교가 불가능한 지점은 비교 문자열의 아스키 코드를 비교 → 각 문자열 중 제일 작은 아스키 코드 값을 뺌