断序搜索

题目

给定一个一排序数组,但这个数组是在一个地方断开的。例如:[7,8,1,2,3,4,5,6],但具体从什么地方断开是不知道的,需要从这个序列中找到一个元素。

分析

这个题目很有意思,从表面上来看不能使用二分之类的方法,但其实情况只是比原来复杂了一些。我们只需要判断断开的点是再左半边还是再由半边即可,在迭代的过程中我们会遇到三种情况:

  1. 搜索范围是顺序元素
    1. 只需要递归查找即可,以后的搜索范围都会是顺序元素
  2. 搜索范围的左半部分是顺序元素
    1. 同样递归查找、缩小范围
  3. 搜索范围的右半部分是顺序元素
    1. 缩小范围将搜索范围挤到顺序范围内,挤到一个元素为止

如何挤?

其实,在我们做二分查找的时候,很容易能确定我们需要的元素在左半部分还是右半部分。我们需要的是在哪个范围内。而在这里正好相反,我们需要确定哪边是顺序元素,然后判断元素不在这个范围内,那必定在另一边。

题解

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int search(int* nums, int numsSize, int target) {
	int l = 0;
	int r = numsSize - 1;

	while (l <= r) {
		printf("%d\n", l);
		int mid = (l + r) / 2;
		if (target == nums[mid]) {
			return mid;
		}
		if (nums[l] <= nums[r]) {
			if (target < nums[mid])
				r = mid - 1;
			else
				l = mid + 1;
		} else if (nums[l] <= nums[mid]) {
			if (target > nums[mid] || target < nums[l])
				l = mid + 1;
			else
				r = mid - 1;
		} else {
			if (target < nums[mid] || target > nums[r])
				r = mid - 1;
			else
				l = mid + 1;
		}
	}
	return -1;
}

int main(void) {
	int lists[] = {1, 3, 5 };
	int res = search(lists,3, 1);
	printf("res = %d\n", res);
	return EXIT_SUCCESS;
}