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.