在旋转数组中查找指定值（2）--- 线性表

【描述】

跟进“在旋转排序数组中搜索”：如果运行重复怎么办？

这会影响运行时的复杂度吗？如何以及为什么？

编写一个数组来确定给的目标是否在数组中；

【分析】

1. 允许重复元素，则上一题中如果arr[start] <= arr[mid],那么[start, mid]为递增序列的假设就不能成立了，比如[1, 3, 1, 1, 1];

2. 如果arr[mid] >= arr[start]不能确定递增，那就把他拆为两个条件：

1> 若arr[mid] > arr[start]， 则区间[start, mid]一定递增；

2> 若arr[mid] = arr[start]确定不了，那就start++,往下一步即可；

3. 时间复杂度 O(n)，空间复杂度 O(1)

注意：具体实现参考代码；

【代码实现】

//demo.h
int search_ex(int arr[], int len, int target);

//demo.c
int search_ex(int arr[], int len, int target)
{
	int start = 0;
	int end = len;

	if (len <= 0) {
		return -1;
	}

	while (start != end)
	{
		const int mid = (start + end) / 2;
		if (arr[mid] == target) {
			return mid;
		}

		if (arr[start] < arr[mid]) {
			if (arr[start] <= target && target < arr[mid]) {
				end = mid;
			}
			else {
				start = mid + 1;
			}

		}
		else if (arr[start] > arr[mid]) {
			if (arr[mid] < target && target <= arr[end - 1]) {
				start = mid + 1;
			}
			else {
				end = mid;
			}
		}
		else {
			start++;
		}
	}

	return -1;
}