问题:对已排好序的数组A,一般来说可用二分查找 可以很快找到。现有一特殊数组A[],它是循环递增的,如A[]={ 17 19 20 25 1 4 7 9},试在这样的数组中找一元素x,看看是否存在。
思路:同样用二分查找,每次用待查找元素x与中间元素比较,如果大于中间元素,则left=middle+1,如果小于中间元素,需比较x与左边元素的大小,如果大于左边元素,则right=middle-1,否则left=middle+1。
复制代码
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
27int findx(int *a, int len, int key) { int left, right, middle; left = 0; right = len - 1; while(left <= right) { middle = (left + right) / 2; if(key > a[middle]) { left = middle + 1; } else if(key < a[middle]) { if(key < a[left]) { left = middle + 1; } else { right = middle - 1; } } else return 1; } return 0; }
最后
以上就是酷炫导师最近收集整理的关于笔试之循环递增数组查找的全部内容,更多相关笔试之循环递增数组查找内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复