이진 검색 - 중복요소의 맨 앞 인덱스 찾아내기 | 반복문의 유연한 사용이 필요하겠다.

이전에 봐왔던 이진검색에서는 중복 요소가 있을 경우에 중간인덱스를 리턴하는 구조이다. 갱신되는 구간의 중간인덱스와 찾는key값을 비교하는 방식이기 때문이다. 

 

다음 사진을 보자. 동일 요소들 7중에서 7을 찾는 이진 탐색 결과, 중간 인덱스를 리턴한다. 

 

 

 

하지만 이번에 풀어볼 문제에서는 중복요소의 중간 인덱스를 리턴하는 것이 아니라, 중복 요소 중 맨 앞의 인덱스를 찾아내는 것이 목적이다. 문제는 다음과 같다. 

 

 

(Doit! 자료구조와 함께 배우는 알고리즘 입문 자바편 117페이지 연습문제 )

이진검색 알고리즘 프로그램 문제

 

 

그냥 일반적인 이진검색 후에 리턴되는 인덱스에서부터 앞쪽으로 쭉 스캔하면 되는 문제다. 

굉장히 간단하게 해결가능하다. 단지 그냥 아래 사진에서 하이라이트 친 부분처럼만 작성해주면 되잖아!!

 

이진탐색 - 맨앞 인덱스를 반환

 

이진탐색의 결과로 나온 key값의 인덱스 pc는 중복요소key의 중앙인덱스다. 그러니까 앞에서부터 pc까지 다시 선형검색하면 된다. 하지만 문제에서는 이렇게 언급하고 있다. "그 위치(pc)로부터 하나씩 검사". 즉, 저렇게 인덱스0부터 선형으루 쭉 검사하는 걸 의도한 게 아니라, pc에서부터 인덱스0 방향으로 검사하라는 뜻이다. 그럼.. 반대로 이렇게 해주면 되는 것 아닌가욘~~

 

아무튼 이렇게 나는 그냥 일반적인 이진탐색을 완료한 뒤에 인덱스를 앞으로 하나씩 옮기면서 앞에 중복요소가 더 있는지 검사해줬는데, 답안은 아래와 같다.

 

 

"핵심: 어차피 이진탐색은 순차적 정렬 상태가 전제다"

 

이진탐색 과정 중 a[pc]==key 이라는 조건 하에서 for문을 돌려 key보다 작을 때까지 pc를 줄여나갔다. 굳이 나처럼 변수 f_idx같은 걸 만들지 않아도 돼서 깔끔해보인다. for문 안에서 새로운 변수선언 (int i=0;)을 하지 않는 경우라는 걸 유의하자. 그냥 이미 있는 변수인 pc를 가지고, 원하는 조건 a[pc-1]<key를 만족할 때까지 반복하면 된다. 저 조건에 다다르면 반복을 멈추는 break를 걸면 되는 것이다. 

 

if (a[pc] == key) {
	for (; pc > pl; pc--) // key와 같은 맨 앞의 요소를 찾습니다
		if (a[pc - 1] < key)
			break;
	return pc; // 검색성공
}

 

 

for문을 이렇게 활용가능한 것임을 새겨두자. 나는 지금까지 초보의 전형적인 유일한 for문사용을 했었다. 이번 답안을 보니 내가 for문에 대한 생각이 많이 닫혀있었음을 깨닫는다. 반복문을 조금 더 유연하게 생각하고 많은 경우를 접해보는 것이 중요하겠다.