2. 이진검색과 정렬(Java)

Algorithm/Algorithm Practice

2. 이진검색과 정렬(Java)

GrapeMilk 2020. 2. 25. 22:15

Goal

- 이진검색의 이해

- 이진검색 알고리즘 C언어 및 Java언어로 구현

- 정렬의 이해 및 시간복잡도 비교

1. 이진검색과 정렬

1-1 이진검색 (Binary Search)

- 제어 검색의 일종인 이진 검색은 반드시 순서화된 파일이어야 검색할 수 있다.

- 찾고자하는 값을 파일의 중간 값과 비교하며 검색함

- 반쪽을 찾아보고 없으면, 크기 비교를 통해 왼쪽 또는 오른쪽으로 방향을 설정하고 나머지 반쪽에서 찾아가면서 범위를 점점 반씩으로 줄여가는 방법

- 배열의 첫 값을 보통 First 마지막 값은 Last 중간값은 Middle이라고 함.

예제1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15와 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14를 찾는 경우 비교되는 횟수는? (답 : 3번)

1) 문자열 배열 data에서 target값의 index 찾기 예제 코드

- 배열 data에 n개의 문자열이 오름차순으로 정렬되어 있음

- 한 번 비교할 때마다 남아있는 데이터가 절반으로 줄어들기 때문에 시간복잡도는 O(log2n)이다.

int binarySearch(int n, char *data[], char *target) { //* 포인트 변수 선언. &(주소연산자)를 통해 주소를 저장 할 수 있음)
  int begin = 0, end = n-1;
  while(begin <= end) {
    int middle = (begin + end) / 2;
    int result = strcmp(data[middle], target);
    if (result == 0)
      return middle;
    else if (result < 0)
      begin = middle + 1;
    else
      end = middle - 1;
  }
  return -1;
}

/*
strcmp(s1, s2);와 같이 strcmp 함수에 비교할 문자열을 넣어주면 결과를 정수로 반환(문자열을 비교할 때 대소문자를 구분함).

-1: ASCII 코드 기준으로 문자열2(s2)가 클 때
0: ASCII 코드 기준으로 두 문자열이 같을 때
1: ASCII 코드 기준으로 문자열1(s1)이 클 때
*/

1-1) Java로 구현

package inflearn.chapter1.algorithm;

import java.util.Arrays;
import java.util.Scanner;


public class BinarySearchImplement {

	public static void main(String[] args) {
	
	//  Scanner sc = new Scanner(System.in);
	  String[] str = {"kim", "berry", "back", "cris", "zcd", "jace", "jill"};
	  Arrays.sort(str); // 배열을 '가나다' 또는 'abc'순으로 정렬, int형 배열을 입력하면 '오름차순'정렬
	  System.out.println(Arrays.toString(str)); // for test
	  System.out.println(binarySearch(str.length, str, "jace"));
	  
	  
	 
	}
	
	static int binarySearch(int n, String[] data, String target) {
		
	  int first = 0, last = n-1;
	  while(first <= last) {
	    int middle = (first + last) / 2;
	    int result = data[middle].compareTo(target);
	    if (result == 0)
	    	return middle;
	    else if (result < 0)
	    	first = middle + 1;
	    else 
	    	last = middle - 1;
	  }
	  return -1;
	}
	
}


/*
 * String 배열 출력 (Arrays.toSting())
 * 배열 오름차순, 내림차순 정리 (Arrays.sort() / Arrays.sort()이후 
*/