Y/search-in-rotated-sorted-array.linq at master · BigMuzzy/Y · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
<Query Kind="Program" />

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

void Main()
{
	int[] m1 = { 4, 5, 6, 7, 0, 1, 2 };
	int[] m2 = {  };

	Search(m2, 1).Dump();
}

int Search(int[] nums, int target)
{
	int pivot = FindPivot(nums, 0, nums.Length - 1).Dump();
	//search left
	int result = BinarySearch(nums, 0, pivot, target);
	//search right
	if (result < 0)
	{
		result = BinarySearch(nums, pivot + 1, nums.Length - 1, target);
	}

	return result;
}

int FindPivot(int[] nums, int l, int r)
{
	if (l > r)
	{
		return -1;
	}

	if(l == r)
	{
		return l;
	}

	int mid = l + (r - l) / 2;
	if (nums[mid] > nums[mid + 1])
	{
		return mid;
	}

	if (nums[mid] < nums[l])
	{
		return FindPivot(nums, l, mid - 1);
	}

	return FindPivot(nums, mid + 1, r);
}

int BinarySearch(int[] nums, int l, int r, int target)
{
	if (l > r)
	{
		return -1;
	}

	int mid = l + (r - l) / 2;

	if (nums[mid] == target)
	{
		return mid;
	}

	if (nums[mid] > target)
	{
		return BinarySearch(nums, l, mid - 1, target);
	}

	return BinarySearch(nums, mid + 1, r, target);
}