34-moran991231.md

34. Find First and Last Position of Element in Sorted Array

Solution 1

시간복잡도 : O(logN)

알고리즘 : Binary Search

풀이 설명 :

오름차순으로 정렬된 배열nums에 target 값이 존재하는지, 존재한다면 배열의 몇 번 인덱스부터 몇 번 인덱스까지 존재하는지 찾는 문제이다.

반환값은 target이 nums에 존재하는 인덱스의 최솟값(i_min)과 최댓값(i_max)이다.

1. 주어진 배열 nums가 빈 배열인 경우: {-1,-1}리턴
2. 주어진 배열 nums의 길이가 1인 경우: 0번 원소 검사 후 target이 없으면 {-1,-1}, 있으면 {0,0} 리턴
3. 첫 번째 while문: target이 nums에 존재하는 인덱스의 최댓값 찾기 r[1]
4. 첫 번재 while문에서 target값을 찾지 못해서 e<s가 되면 {-1,-1}을 리턴
5. 두 번째 while문: target이 nums에 존재하는 인덱스의 최솟값 찾기 r[0]

while문이 이진탐색 코드이다. 배열에서 값의 존재여부만 찾는 기본적인 이진탐색과 거의 비슷하다. 다른점을 살펴보자.

• nums[idx]==target과 같이 == 연산이 아닌, <=혹은 >=의 비교연산이 사용되었다. ==이 없는 이유는 nums 배열에서 target값을 발견해도 탐색을 멈추지 않고 인덱스의 하한/상한을 탐색하기 위함이다.
• s=idx, e=idx 가 사용되었다. 기존의 이진탐색은 s=idx+1, e=idx-1이 사용되었다. 이는 nums[idx]과 target의 값을 비교하고 다음 탐색에서 nums[idx]를 제외하기 위함인데, 아래 코드에서는 ==연산이 아닌 <=, >=연산을 사용하였으므로 nums[idx]를 다음탐색에서도 포함시켜야 한다.
• if(s==idx){...} , if(e==idx){...} 가 존재하는 이유는 s=idx, e=idx가 사용되었기 때문이다. 기존의 이진탐색은 s=idx+1, e=idx-1이 사용되어서 (배열에 target값이 없을 경우) e<s가 되어 while문을 탈출한다. 그러나 아래의 코드에서는 if(s==idx){...} , if(e==idx){...} 를 이용해서 while문을 탈출하지 않으면 무한loop에 갇혀버린다.
• if(s==idx){...} 의 내용은 다음과 같다. nums[idx+1]이 target이면 r[1]=idx+1, nums[idx]이 target이면 r[1]=idx, 둘 다 아니면 nums에 target이 없으므로 {-1,-1}을 리턴한다. idx뿐만 아니라 idx+1 인덱스도 검사한 이유는 s==idx이고 e==idx+1인 경우를 위해서이다. idx+1이 nums의 인덱스 범위를 벗어나는 경우는 없다. (nums의 길이가 1일 때 인덱스 범위 에러가 발생할 수 있어서 while문에 진입하기 전에 예외처리해주었다.)
• if(e==idx){...}의 내용은 다음과 같다. nums[idx-1]과 nums[idx] 중에 target값이 존재하는지 검사하고 r[0]에 idx-1과 idx중 적절한 값을 넣는다. if(s==idx){...} 에서와 달리 {-1,-1}의 리턴문이 없다. targe이 존재하지 않는 경우는 이미 첫 번째 while문에서 걸러졌기 때문이다. 또한 여기서는 e==idx이기 때문에 idx-1과 idx를 검사한다. 배열의 인덱스 범위 에러를 피하기 위해 while문 첫 명령문에 idx=(s+e+1)/2를 해주었다.

소스코드 :

class Solution {

	public static int[] searchRange(int[] nums, int target) {
		int s = 0, e = nums.length - 1, idx;
		int[] ret = { -1, -1 };
		if (e < 0)
			return ret;
		if (e == 0) {
			ret = (nums[0] == target) ? new int[2] : ret;
			return ret;
		}

		while (s <= e) {
			idx = (s + e) / 2;
			if (nums[idx] <= target) {
				if (s == idx) {
					if (nums[idx + 1] == target) ret[1] = idx + 1;
					else if (nums[idx] == target) ret[1] = idx;
					else return ret;
					break;
				}
				s = idx;
			} else {
				e = idx - 1;
			}
		}
		if (e < s)
			return ret;

		s = 0;
		e = nums.length - 1;
		while (s <= e) {
			idx = (s + e+1) / 2;
			if (target <= nums[idx]) {
				if (e == idx) {
					if (nums[idx - 1] == target) ret[0] = idx - 1;
					else if (nums[idx] == target) ret[0] = idx;
					break;
				}
				e = idx;
			} else {
				s = idx + 1;
			}
		}

		return ret;
	}
}