2 분 소요

문제

Search in Rotated Sorted Array - LeetCode

내 풀이

class Solution {
    public int lowerBound(int[] nums, int target) {
			int lo = 0;
			int hi = nums.length-1;
			
			while(lo<hi) {
				int mid = (lo+hi)/2;
				if(nums[mid] > target) {
					lo = mid+1;
				}else {
					hi = mid;
				}
			}
			return lo;
		}
    public int search(int[] nums, int target) {
        int n = nums.length;
        // nums 배열에서 최소값 위치 찾기
		int rot = lowerBound(nums, nums[n-1]);
		boolean flag = false;
		// target 찾기 
		int lo = rot;
		int hi = n-1;
		int rst = 0;
		while(lo <= hi) {
			int mid = (lo+hi)/2;
			if(nums[mid]==target) {
				flag = true;
				rst = mid;
				break;
			}else if(nums[mid] > target) {
				hi = mid-1;
			}else {
				lo = mid+1;
			}
		}
		
		if(flag) return rst;
		
		lo = 0;
		hi = rot-1;
		rst = 0;
		while(lo <= hi) {
			int mid = (lo+hi)/2;
			if(nums[mid]==target) {
				flag = true;
				rst = mid;
				break;
			}else if(nums[mid] > target) {
				hi = mid-1;
			}else {
				lo = mid+1;
			}
		}
        
		if(flag) return rst;
		return -1;
    }
}

해설

def search(nums: List[int], target: int) -> int:
    # pivot 찾기 : 최솟값을 찾는 binary search
    def find_pivot(nums):
        lt, rt = 0, len(nums)-1
        while lt < rt:
            mid = (lt+rt)//2
            if nums[mid] > nums[rt]:
                lt = mid+1
            else:
                rt = mid
        return lt

    pivot = find_pivot(nums)
    
    # 피벗 기준 이진검색
    n = len(nums)
    lt, rt = 0,  n-1
    while lt<=rt:
        mid = (lt+rt)//2
        real_mid = (mid+pivot)%n       # 중앙의 위치 mid에서 pivot만큼 이동하고, 배열의 길이를 초과할 경우 %로 회전될 수 있도록 처리
        # 타켓과 값을 비교하는 부분은 mid가 아닌 mid_pivot을 기준으로 하되, left와 right는 mid를 기준으로 이동한다.
        if nums[real_mid] < target:
            lt = mid+1
        elif nums[real_mid] > target:
            rt = mid-1
        else:
            return real_mid
    return -1

    pivot = find_pivot(nums,0,len(nums)-1)
    print(pivot)
    return pivot

lowerbound와 upperbound. (+ lowerbound를 이용하여 rotated array에서 최솟값 위치 찾기)

'''
lowerbound
: (배열에 같은 원소가 여러 개 있을 경우) 찾고자 하는 값 이상이 처음 나타나는 위치
[문제 예시]
n개로 이루어진 정수 집합에서 k 이상인 수가 처음으로 등장하는 위치를 찾으시오.
단, 입력되는 집합은 오름차순으로 정렬되어 있으며 (이분탐색 가능), 같은 수가 여러 개 존재할 수 있다.
'''
import bisect

def lowerbound(arr, key):
    # arr은 정렬되어있다고 가정
    lo, hi = 0, len(arr)-1
    while lo<hi:
        mid = (lo+hi)//2
        if arr[mid] < key:
            lo = mid+1
        else:
            hi = mid
    # while이 끝날때까지 돈다. 도중에 key랑 같으면 return 같은거 안함. -> 당연
    return lo

def upperbound(arr, key):
    lo, hi = 0, len(arr)
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= key:         # 여기만 달라짐
            lo = mid + 1
        else:
            hi = mid
    return lo

arr = [1,2,3,3,4,4,4,5,6,7,8]
key = 4  # 3과 같거나 큰 수가 나오는 첫 위치가 lowerbound이다.
print(lowerbound(arr, key))
print(upperbound(arr, key))

# bisect 모듈 사용
print(bisect.bisect_left(arr, 4))  # lowerbound
print(bisect.bisect_right(arr, 4))  # upperbound

응용 : 아래와 같은 배열에서 최솟값 이상이 처음으로 등장하는 위치를 구해라 O(logN) -> (lowerbound를 이용)


def find_min_loc(arr):
    lo, hi = 0, len(arr)-1
    while lo < hi:
        mid = (lo+hi)//2
        if arr[mid] > arr[hi]:  # 왜?? < 이게 아니지?? => 직접 그려보기
            lo = mid+1
        else:
            hi = mid
    return lo

arr = [5,6,7,8,1,2,3,4]
print(find_min_loc(arr))

참고