[leetcode][C++] search in rotated sorted array

https://leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

 

 

input값은 정렬된 배열이기 때문에 바이너리 서치를 사용할 수 있다.

배열이 시작하는 시점 (정렬이 끝나는 시점)을 찾아서 범위마다 바이너리 서치를 실행해서 풀었다.

 

nums[] = {5 < 6 < 7 > 1 < 2 < 3 < 4}

binarySearch(5~7) / binarySearch(1~4)

 

 

 

[leetcode][C++] search in rotated sorted array

class Solution {
public:
	int binarySearch(int left, int right, vector<int>& nums, int target) {
		int mid;

		while (left <= right) {
			mid = (left + right) / 2;
			// mid = left + (right - left) / 2;	avoid overflow
			if (nums[mid] == target)
				return mid;
			else if (nums[mid] > target)
				right = mid - 1;
			else left = mid + 1;
		}

		return -1;
	}

	int search(vector<int>& nums, int target) {
		int i = 0;
		for (; i < nums.size() - 1; i++) {
			if (nums[i] > nums[i + 1])
				break;
		}

		if (nums[0] <= target && target <= nums[i])
			return binarySearch(0, i, nums, target);
		else
			return binarySearch(i + 1, nums.size() - 1, nums, target);
	}
};