Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바 편 (p.111~115) [ 검색 알고리즘 ]

복잡도 구하기

(1) 시간 복잡도 : 실행에 필요한 시간을 평가한 것

(2) 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

do {
			int pc = (pl + pr) / 2; //O(log n)
			if (a[pc] == key) ////O(log n)
				return pc;
			else if (a[pc] < key) //겁색할 값이 더 크면
				pl = pc + 1; //큰 쪽을 검색 범위로 한정할거야
			else
				pr = pc - 1; //작으면 작은 쪽을 검색 범위로 한정할거야
		} while (pl <= pr);

복잡도의 대소 관계 

: 1 < logn < n < nlogn < n^2 < n^3 < n^k < 2^n

 

Q3.

	//요소수가 n인 배열 a에서 key와 일치하는 모든 요소의 인덱스를 배열 idx의 맨 앞부터 순서대로 저장하고, 일치하는 요소수를 반환하는 메서드
	static int searchIdx(int[] a, int n, int key, int[] idx) {
		int count = 0; //메서드 전역으로 해야지!!
		for (int i = 0; i < n; i++) {
			if (a[i] == key)
				idx[count++] = i; 
		}
		return idx.length+1; //or count를 return해도 무방하다.
	}

Q5.

//이진 검색 알고리즘 프로그램은 검색하라 키값과 같은 값을 갖는 요소가 하나 이상일 경우 그 요소 중 에서 맨 앞의 요소를 찾지 못함 
	//이를 개선해라
	static int binSearchX(int[] a, int n, int key) {
		int pl = 0;
		int pr = n-1;
		
		do {
			int pc = (pl + pr) / 2;
			if(a[pc] == key) { //중간값이랑 키값이 같으면
				//todo : 이전의 인덱스에 같은 키가 있는지를 확인
				int i = pc;
				while (a[i] == key) {
					i--;
				}
				return i;
			}
				
			else if (a[pc] < key) {
				pl = pc + 1;
			}
			else {
				pr = pc - 1;
			}
				
			
					
		} while (pl <= pr);
		return -1;
	}