## Monday, January 7, 2019

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

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

## 문제 링크

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
두단계로 끊어서 생각
시간 복잡도는 O(log n) 인것 같은데 이상하게 느리네 ;;
Runtime: 6 ms, faster than 37.73% of Java online submissions for Find First and Last Position of Element in Sorted Array.

### 1단계

• binary search를 탐색하는거를 만들고
• 로그를 출력하면서 잘 탐색을 하는지 확인
public void find(int start, int end, int[] nums) {
if (end <= start) {
return;
}

int mid = start + (end - start) / 2;
System.out.println(mid);
// lef
find(start, mid, nums);
// right
find(mid + 1, end, nums);
}

// output  ex) new int[]{1,2,3,4,5,6,7}
/**
3
1
0
2
5
4
6
**/

### 2단계

• 1단계를 응용해서 변경
public class FindFirstLast {
int low = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

public int[] searchRange(int[] nums, int target) {

find(0, nums.length, nums, target);

if(low != Integer.MAX_VALUE){
return new int[]{low, max};
}else{
return new int[]{-1, -1};
}

}

public void find(int start, int end, int[] nums, int target){
if(end <= start){
return;
}

int mid = start + (end - start)/2;
//  System.out.println(mid);

if(nums[mid] == target){
low = Math.min(mid, low);
max = Math.max(mid, max);
if(start < low){
find(start, mid, nums, target);
}

if(end > max){
find(mid+1, end, nums, target);
}

}else if(nums[mid] < target){
find(mid+1, end, nums, target);
}else if(nums[mid] > target){
find(start, mid, nums, target);
}

}

public static void main(String args[]){
new FindFirstLast().searchRange(new int[]{1,2,3,4,5,6,7,8}, 5);
}

}
Written with StackEdit.