NAIAHD

03-1 검색 알고리즘 

검색과 키

그 주목하는 항목을 키(key)라고 하겠습니다.

배열에서 검색 

1. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다.

2. 이직 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다.

3. 해시법: 추가 , 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다.

  체인법: 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법

  오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

03-2 선형 검색 linear search sequential search

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때 까지 맨앞부터 순서대로

요소를 검색하는 것

static int seqSearch(int[] a, int n , int key){

  int i = 0

  while(true){

    if(i == n)

      return -1;

    if (a[i] == key)

      return i;

    i++;

  } 

}

int[] x = new int[num];

무한 루프의 구현 

보초 sentinel method

이 비용을 반으로 줄이는 방법 

static int seqSearch(int[] a, int n , int key){

  int i = 0

  a[n] = key;

  while(true){

    if (a[i] == key)

      break;

    i++;

  } 

  return i == n ? -1 : i ;

}

int[] x = new int[num+1];

03-3 이진검색 binary search

요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘입니다.

맨 앞 인데스를 pl , 맨 끝 인덱슬르 pr, 중앙 인덱스를 pc

초기화 pl = 0, pr = n-1, pc = (n-1)/2

1. a[pc] < key 

a[pl] ~ a[pc]는 제외 , 검색 범위는 중앙요소 a[pc]보다 뒤쪽의 a[pc+1] ~ a[pr]

pl값을 pc+1로 업데이트 한다.

2. a[pc] > key 

a[pc] ~ a[pr]는 제외 , 검색 범위는 중앙요소 a[pc]보다 뒤쪽의 a[pl] ~ a[pc-1]

pr값을 pc-1로 업데이트 한다.

이진 검색은 검색을 반복할 때 마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 

평균값은 log n이다.

이진 검색 알고리즘은 검색 대상(배열)되어 있음을 가정합니다.

static int binSearch(int[] a, int n , int key){

  int pl = 0

  int pr = n-1;

  do{

    int pc = (pl+pr)/2;

    if (a[pc] == key)

      return pc;

    else if(a[pc] < key)

      pl = pc+1;

    else 

      pr = pc -1 

  }while(pl <= pr);

  return -1;

}

복잡도 

알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도 (complexity)라고 합니다.

1. 시간 복잡도 time complexity: 실행에 필요한 시간을 평가하는 것

2. 공간 복잡도 space complexity : 기억 영역과 파일 공간이 얼마나 필요한가를 평가 하는 것 

선형 검색의 시간 복잡도  O(n)

평균 실행 횟수는 n/2입니다.

 이진 검색의 시간 복잡도 

static int binSearch(int[] a, int n , int key){

  int pl = 0

  int pr = n-1;

  do{

    int pc = (pl+pr)/2;

    if (a[pc] == key)

      return pc;

    else if(a[pc] < key)

      pl = pc+1;

    else 

      pr = pc -1 

  }while(pl <= pr);

  return -1;

}=>O(log n)

Arrays.binarySearch에 의한 이진 검색 

binarySearch

장점 1 . 이진 검색 메소드를 직접 코딩할 필요가 없다.

장점 2 . 모든 자료형 배열에서 검색 할 수 있다.

검색에 성공한 경우 : key와 일치하는 요소의 인덱스를 반환

검색에 실패한 경우 x라고 할 떄 -x-1

기본 자료형 배열에서 binarySearch메소드로 검색하기

클래스 메서드와 인트턴스 메서드

인스턴스 메서드 (비정적 메서드) static붙이지 않고 선언한 메소드

클래스 메서드(정적 메서드) static 을 붙여 선언한 메소드

둘의 차이점은 메서드가 인스턴스에 포함되는지'의 여부에 있습니다.

자연 정렬 : 사람에게는 오른쪽 형태의 정렬이 더 자연스럽습니다. 바로 이 정렬을 자연 정렬 이라고 한다.

파라미터 이름 작성 :

1. 1개의 대문자를 사용합니다.(소문자는 가급적 사용하지 않습니다.)

2. 컬렉션의 자료형은 element의 앞글자인 E를 사용합니다.

3. 맵의 키 , 값은 key와 value의 앞글자인 K와 V를 사용합니다.

4. 일반적으로는 T를 사용합니다.

출처 : Do it ! 자료구조와 함께 배우는 알고리즘 입문 자바편