[LeetCode] - M - Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

Search in Rotated Sorted Array - LeetCode

 

📌 - 풀이

1. 2가지의 경우로 나눠서 Binary Search를 함
2.  1) nums[mid] 값이 nums[start]보다 작을 경우 -> 이럴 경우 mid의 아래의 값은 정렬되어 있지 않고 mid위의 값들은 정렬되어 있는 상태이므로 위의 값들과 비교해서 start와 end를 조정
3.  2) nums[mid]값이 nums[start]보다 크거나 같을 경우 ->  mid 아래의 값이 적어도 정렬되어 있기 때문에 아래의 값들로 start와 end값을 조정 
4. 이 반복을 start가 end보다 작을때까지 반복
5. 끝났을 때 num[start]의 값과 target이 같으면 start반환 아닐경우 -1 반환 

 

이분탐색 같은 경우는 start값과 end, mid값들을 다루는 게 생각보다 쉽지 않은 것 같음. 조건문의 경우에도 다양한 조건에 대해서 확실하게 하고 넘어가야 맞기 때문에 생각을 더 많이 해봐야 할 것 같음

 

🔥 - Java 코드

 

class Solution {
    public int search(int[] nums, int target) {
        
        int start =0;
        int end = nums.length-1;

        while(start < end){
            int mid = (start + end)/ 2;
            if(nums[mid] < nums[start]){
                if(nums[mid] <= target && nums[end] >= target){
                    start = mid;
                }else{
                    end = mid-1;
                }
            }else{
                if(nums[mid] >= target && nums[start] <= target){
                    end = mid;
                    
                }else{
                    start = mid+1;
                }

            }
        }

        if(nums[start] == target){
            return start;
        }else{
            return -1;
        }
        
    }
}