题目

【加试题】“轮转后有序数组（Rotated Sorted Array）”是将有序数组其中某一个数为分割点，将其之前的所有数都轮转到数组的末尾所得。比如{7，11，13，17，2，3，5}就是一个轮转后的有序数组，原有序数组中的字串{2，3，5}被轮转到了数组的末尾处。 对于一个轮转后有序数组arr也可以进行二分查找，算法思路如下（以升序为例）：每次根据查找的左侧位置L和右侧位置 R 求出中间位置M后，M左边[L，M]和右边 [M+1，R]这两部分中至少一个是有序的（可根据中间位置数据和边界数据的大小关系判 断）。 arr[M]和待查找数据key比较 ⑴arr[M]=key，返回M的值； ⑵若M位置右侧有序，当待查找数据在右侧，则下次在右侧查找，否则在M左侧查找。 ⑶若M位置左侧有序，当待查找数据在左侧，则下次在左侧查找，否则在M右侧查找。 问题： （1） 对于轮转后有序数组{7，11，13，17，2，3，5}使用以上函数 search()查找key值3，所需要的查找次数为。 （2） 以下VB函数 search()实现了对轮转后有序数组arr进行二分查找的过程，如果查询 成功，返回M值，查询失败则返回-1。请补充程序①②③划线处的代码。 Function search(key As Integer, L As Integer, R As Integer) As Integer Do While L <= R And search = -1     M = (L + R) \ 2     If arr(M) = key Then         search = M     Else         If     Then             If arr(L) <= key And key < arr(M) Then                 R = M - 1             Else                 L = M + 1             End If         Else             If  Then                 L = M + 1             Else                 R = M - 1             End If         End If     End If Loop End Function 答案： 【1】2 【1】search = -1【2】arr(M) > arr(R)【3】arr(M) < key And key <= arr(R)

查看本题答案和解析