자료구조 08 - 이진 검색
이전시간에 작성했던 선형검색은 데이터를 맨앞에서부터 차례대로 검색해 key값을 찾는 것이였다.
이번 시간에 작성할 이진검색은 선형검색과 다르게 전제조건이 존재한다.
전제조건은 데이터가 sort(정렬) 되어 있다고 가정 후 검색을 하는 것이다.
코드를 짜기전 위의 도식화된 그림을 그리고 코드를 작성했다.
양쪽 인덱스의 값의 평균을 중앙값으로 계산하여 이진검색의 기준을 잡았다.
위에 도식화를 기준으로 이진 검색 코드를 작성해 보았다.
import java.util.Scanner;
class binary_search{
public static int Binary_search(int [] A, int key){
int str =0;
int fin = A.length-1;
if(key == A[0]){
return 1;
}
if(key==A[fin]){
return fin+1;
}
int mid = 0;
do{
mid = (str+fin)/2;
if(a[mid]>key){
fin = mid-1;
}
else if (A[mid]<key){
str = mid +1;
else{
return mid+1;
}
}while(str<=fin);
return -1;
}
public static void main(String[] args){
Scanner = scan = new Scanner(System.in);
int[] testing = new int[]{1,3,4,10,13,15,17,25,26,33,37};
System.out.println("찾는값은?");
int key = scan.nextInt();
int Answer = Binary_search(testing,key);
System.out.println(Answer!=-1? "찾는값은" + Answer + "번째에 있습니다" : " 찾는값은 없습니다");
}
}
아래는 위의 코드를 실행해본 결과이다.
이진검색에 대한 코드를 작성해 본것이다
처음에 while( start != fin)으로 놓아 못찾는값이 존재했었음
위처럼 한다면 start == fin일때 while문을 통과하지못하고 값을 뽑아낼수가 없어 값이 존재하지 않도록 나온다.
그래서 start<=fin으로 바꾸어 fin== start일때도 값의 판단이 가능하도록 하였다.
위의 이진 검색의 시간복잡도를 O(logn)이라고 하는데
이것의 의미는( 오른쪽 절반짜르고 절반짜르고 절반짜르고
-> 원하는값 찾을때까지 데이터가 1/2씩 줄어들기 때문)
전글에서 사용한 선형검색은 시간복잡도가 O(n)인데
-> 처음부터 끝까지 원하는 값찾기위해 n번의 계산을 진행할것이기 때문
복잡도란
1. 시간 복잡도 - 실행시간에대한 복잡도
2. 공간 복잡도 -기억의 영역에 대한 복잡도
->알고리즘의 효율성을 판단하기위해 복잡도 라는 개념이 나왔다.
클래스 메소드 vs 인스턴트 메소드
위에에 코드를 작성하다 non-static method오류가 발생해 이유를 알아보았다.
클래스 메소드
- static을 붙이고 객체를 생성하지 않고 메소드이름으로 호출 가능 클래스 외부에선 클래스.메소드로 -> 인스턴스 변수와 관계없는 메소드
인스턴스 변수를 사용할 수 없고
변수에 static을 붙인다면 -> 객체 없이 사용될수없으며 객체를 이용해서도 사용할수 있는 클래스에서 전부 사용가능한 변수가 된다.
ex static final int MAX = 100; (클래스 내에서 MAX = 100이라는 객체도 클래스메소드도 사용가능하나 변화시킬수 없는 변수)
인스턴스 변수를 사용하지 않는 함수는 static을 붙이는게 메소드 호출시간이 짧아져서 효율증가하기 때문에 고려해봐야 함
클래스 변수는 모두가 공유해 한객체가 바꾼다면 변수가 바뀌게됨
==> 클래스이름.메소드로 호출(클래스 밖에선) , 메소드로 호출 (클래스 안에선)
인스턴스 메소드 - 객체를 생성해야만 호출 가능
==> 클래스 객체명.메소드이름 으로 호출