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

주어진 num 범위 안에서 타겟 에 해당하는 범위를 출력하는것이다. 이미 정렬 되어진 상태이니 이분탐색으로 빠르게 해당 값을 찾고 

그 값으로 부터 좌우로 증가하면서 알맞은 값을 찾는것이다.

코드를 보자.

class Solution {
  public int[] searchRange(int[] arr, int target) {
    int left = -1;
    int right = -1;

    int nLeft = 0;
    int nRight = arr.length - 1;
    int idx = -1;
    while (nLeft <= nRight) {
      int mid = nLeft + (nRight - nLeft) / 2;
      if (arr[mid] < target) {
        nLeft = mid + 1;
      } else if (arr[mid] == target) {
        idx = mid;
        break;
      } else {
        nRight=mid-1;
      }
    }
    if (idx == -1)
      return new int[] { left, right };
    left = idx;
    right = idx;
    while (arr[left] == target) {
      if (left-1>=0 &&arr[left - 1] == target) {
        left--;
      } else {
        break;
      }
    }
    while (arr[right] == target) {
        if(right+1 >= arr.length){
            break;
        }
      if (right+1<arr.length && arr[right + 1] == target) {
        right++;
      } else {
        break;
      }
    }
    System.out.println(left + " " + right);
    return new int[] { left, right };
  }
}

left , right 는 -1 로 지정을 해주고 문제에서 못찾으면 -1 리턴 하라고 했으니 이니셜 지정 해주자. 가운데 값을 찾은 후 말그대로 while 돌려가며 왼쪽 끝 오른쪽 끝을 이동하며 찾는데 12 ms ~ 15ms 정도 나온다. 매우 느린 코드다 마음에 들지 않는다. 양쪽으로 이분탐색을 다시해봐도 별반 차이가 없다... ㅎㅎ

고수들의 코드를 봐보자.

public class Solution {
public int[] searchRange(int[] nums, int target) {
    int[] result = new int[2];
    result[0] = findFirst(nums, target);
    result[1] = findLast(nums, target);
    return result;
}

private int findFirst(int[] nums, int target){
    int idx = -1;
    int start = 0;
    int end = nums.length - 1;
    while(start <= end){
        int mid = (start + end) / 2;
        if(nums[mid] >= target){
            end = mid - 1;
        }else{
            start = mid + 1;
        }
        if(nums[mid] == target) idx = mid;
    }
    return idx;
}

private int findLast(int[] nums, int target){
    int idx = -1;
    int start = 0;
    int end = nums.length - 1;
    while(start <= end){
        int mid = (start + end) / 2;
        if(nums[mid] <= target){
            start = mid + 1;
        }else{
            end = mid - 1;
        }
        if(nums[mid] == target) idx = mid;
    }
    return idx;
}

이분탐색 을 이렇게 반반 나눠서 한다. 와 미쳤다.. 생각 하지도 못했다.... 정형화된 이분탐색 에서 break else 에 변화를 주고 점점 가지치기 해나가는데 와... 멋진 코드이다.

public class Solution {
	public int[] searchRange(int[] A, int target) {
		int start = Solution.firstGreaterEqual(A, target);
		if (start == A.length || A[start] != target) {
			return new int[]{-1, -1};
		}
		return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};
	}

	//find the first number that is greater than or equal to target.
	//could return A.length if target is greater than A[A.length-1].
	//actually this is the same as lower_bound in C++ STL.
	private static int firstGreaterEqual(int[] A, int target) {
		int low = 0, high = A.length;
		while (low < high) {
			int mid = low + ((high - low) >> 1);
			//low <= mid < high
			if (A[mid] < target) {
				low = mid + 1;
			} else {
				//should not be mid-1 when A[mid]==target.
				//could be mid even if A[mid]>target because mid<high.
				high = mid;
			}
		}
		return low;
	}
}

와 이건 ㅋㅋㅋㅋㅋㅋ 아이디어의 발상이 참 대단하다. 찾고자 하는수에 +1 을 해서 그수를 찾고 그인덱스 -1 과 찾고자 하는 수 와 정말 멋진코드가 많다. 이걸보고 다시 내 코드보니 왜이리 구려보이 는지..... 내일 다시풀때는 이 코드로 작성해보자.