在包含2个排序部分的列表中进行二进制搜索

Question

我知道二进制搜索只适用于排序列表。你知道吗

我想搜索（O（logn））并能够在一个包含2个排序部分的列表中找到一个项目。你知道吗

例：[20,30,1,2,3,4,5]

O（logn）二进制搜索是唯一的选择吗？你知道吗

我想在失去顺序的地方拆分列表，但是，随着列表大小的改变，它将不再是我想要的那样复杂？你知道吗

Answer 1

对于这个特殊的问题，有多种方法，它们可以为您提供O（logn）解决方案-

1. 正如@joran所提到的，您可以首先在O（logn）中搜索列表中的分割点，然后在两个列表上再次执行二进制搜索，从而导致O（logn）的总体复杂性。你知道吗

2. 您可以在一次二进制搜索中搜索列表中的元素，只需稍微改变一下逻辑。如以下守则所述—

   # Search an element in sorted and rotated array using
   # single pass of Binary Search
   
   # Returns index of key in arr[l..h] if key is present,
   # otherwise returns -1
   def search(arr, l, h, key):
       if l > h:
           return -1
   
       mid = (l + h) // 2
       if arr[mid] == key:
           return mid
   
       # If arr[l...mid] is sorted
       if arr[l] <= arr[mid]:
   
           # As this subarray is sorted, we can quickly
           # check if key lies in half or other half
           if key >= arr[l] and key <= arr[mid]:
               return search(arr, l, mid - 1, key)
           return search(arr, mid + 1, h, key)
   
       # If arr[l..mid] is not sorted, then arr[mid... r]
       # must be sorted
       if key >= arr[mid] and key <= arr[h]:
           return search(a, mid + 1, h, key)
       return search(arr, l, mid - 1, key)
   
   
   # Driver program
   arr = [4, 5, 6, 7, 8, 9, 1, 2, 3]
   key = 6
   i = search(arr, 0, len(arr) - 1, key)
   if i != -1:
       print ("Index: %d" % i)
   else:
       print ("Key not found")
   

要查看第一种方法的代码，请查看下面的post-https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/