[算法] 循环有序数组查找

浏览数：22 / 时间：2015年06月08日

有序数组二分查找的变形，代码如下：

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



int main() {
	
	int *array = (int *)malloc(sizeof(int)*16);
	int i;
	for(i = 0; i < 16; i++) {
		*(array + i) = (i+5) % 16;
	}
	
	int ret = search(array, 16, 10);
	printf("%d", ret);

	return 0;
}

int isOrdered(int *array, int begin, int end) {
	return *(array+end) > *(array+begin) ? 1 : 0;
}

int contains(int *array, int begin, int end, int theNum) {
	return theNum >= *(array + begin) && theNum <= *(array + end) ? 1 : 0;
}

int CyclicOrderedBinarySearch(int *array, int begin, int end, int theNum) {
	if(begin == end) {
		if(*(array + begin) == theNum) {
			return begin;	
		} else {
			return -1;	
		}
	}
	
        int mid = (begin + end) / 2;	
	if(isOrdered(array, begin, mid)) {
		if(contains(array, begin, mid, theNum)) {
			return CyclicOrderedBinarySearch(array, begin, mid, theNum);	
		} else {
			return CyclicOrderedBinarySearch(array, mid + 1, end, theNum);	
		}
	
	
	} else {
		if(contains(array, mid + 1, end, theNum)) {
			return CyclicOrderedBinarySearch(array, mid + 1, end, theNum);
		} else {
			return CyclicOrderedBinarySearch(array, begin, mid, theNum);	
		}
	}
	return -1;
}



int search(int *array, int n, int theNum) {
	return CyclicOrderedBinarySearch(array, 0, n - 1, theNum);
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

[算法] 循环有序数组查找