循环有序数组查找

Posted on In

相对于利用二分查找在有序数组中查找目标来说。
在循环有序数组中查找目标会更复杂一点。
循环有序数组指的是数组是分段有序的(且假设只有两段)。

在查阅学习后整理了本版本Python3.6的实现。

具体实现思路：依据定义，循环有序数组具有一个性质就是对原数组进行中间切分之后会形成两个数组，一个是有序数据，另外一个是比原循环有序数组更小的一个循环有序数组。

所有利用这个性质实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 循环有序(递增)序列查找
# 循环有序区间的性质：从中间将原序列进行切分，会得到一个有序序列和一个更小的循环序列。
## 同样采用二分查找的思路，只是多做一步，在采取中间拆分的时候需要多判断一步是否是递增
def cycle_binary_serch(alist, target):
    low = 0
    high = len(alist) - 1
    while low <= high:
        mid = (low + high)//2
        if alist[mid] == target:
            return mid;
        if alist[low] <= alist[mid]: # 若前半部分是有序的
            if (alist[low] <= target) and (target < alist[mid]): #  判断目标值是否在有序区间
                high = mid - 1  #  若目标在有序区间范围，则在有序区间中查找
            else:
                low = mid + 1  #  若目标不在有序区间范围，则在另一循环有序区间查找
        else:  # 若后半部分是有序的
            if (alist[mid] < target) and (target <= alist[high]):  # 判断目标是否在有序区间
                low = mid + 1  # 若目标在有序区间，则在有序区间中查找
            else:
                high = mid - 1  # 若目标不再有序区间，则在另一循环有序区间查找

cycle_binary_serch([5,6,30,1,2,3,4],3)

另附二分查找实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 二分查找
## 注意：需要针对的是有序的序列。
## 流程：截取中间的值与目标值匹配，查看值在那个区间，然后以1/2的速度缩小搜索区间。以达到加快搜索的目的。
def binary_search(alist,target):
    low = 0
    high = len(alist) - 1
    while low <= high:
        mid = (low + high)//2
        guess = alist[mid]
        if guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
        else:
            return mid
binary_search([1,2,3,4,5,6,30,10],30)