# 【Python】抛砖引玉-连续有序数组的排序问题

[本文出自天外归云的博客园]

python我的解法是这样的，先把那个分界点找出来，然后切成两个数组，判断下该在哪个数组里进行二分查找，然后进行二分查找：

# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
def find_sub_arr(_arr):
sub_arr1 = []
sub_arr2 = []
i = 0
while i < len(_arr) - 1:
if _arr[i+1] != _arr[i] + 1:
sub_arr1 = _arr[:i+1]
sub_arr2 = _arr[i+1:]
i += 1
return sub_arr1, sub_arr2

def binary_search(_arr, l, r, _num):
if r >= l:
mid = int(l + (r - l)/2)
if _arr[mid] == _num:
return mid
elif _arr[mid] > _num:
return binary_search(_arr, l, mid-1, _num)
else:
return binary_search(_arr, mid+1, r, _num)
else:
return -1

def index_of(_arr, _num):
sub1, sub2 = find_sub_arr(arr)
if _num >= sub1[0]:
print(f"find {_num} in {sub1}")
return binary_search(sub1, 0, len(sub1)-1, _num)
elif _num >= sub2[0]:
print(f"find {_num} in {sub2}")
return len(sub1) + binary_search(sub2, 0, len(sub2)-1, _num)
else:
return -1

arr = [7,8,9,1,2,3,4,5,6]
print(f"arr is {arr}")
for a in arr:
ind = index_of(arr, a)
print(f"index {a} is {ind}")
print("——————————————————")

Original: https://www.cnblogs.com/LanTianYou/p/16373751.html
Author: 天外归云
Title: 【Python】抛砖引玉-连续有序数组的排序问题

(0)