Python에서 주어진 bitonic 시퀀스에서 bitonic 포인트 찾기

<시간/>

Bitonic 시퀀스가 있다고 가정하고 Bitonic Point를 찾아야 합니다. 우리가 알고 있듯이 Bitonic Sequence는 처음에는 엄격하게 증가하고 특정 지점 이후에는 엄격하게 감소하는 숫자의 시퀀스입니다. 이 포인트는 바이토닉 포인트입니다. 증가하거나 감소하는 시퀀스의 경우에만 비트코인 포인트를 사용할 수 없습니다.

따라서 입력이 [7, 8, 9, 12, 10, 6, 3, 2]와 같으면 출력은 12

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

binary_search(array, l, r) 함수 정의
l <=r이면 -
- m :=(l + r) / /2
배열[m - 1] <배열[m] 및 배열[m]> 배열[m + 1]이면 −
- 반환 m
배열[m] <배열[m + 1]이면 -
- binary_search(배열, m + 1, r)를 반환
그렇지 않으면
- binary_search(배열, l, m - 1) 반환
반환 -1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def binary_search(array, l, r):
   if (l <= r):
      m = (l + r) // 2;
      if (array[m - 1] < array[m] and array[m] > array[m + 1]):
         return m;
      if (array[m] < array[m + 1]):
         return binary_search(array, m + 1,r);
      else:
         return binary_search(array, l, m - 1);
   return -1;
array = [7, 8, 9, 12, 10, 6, 3, 2]
n = len(array);
index = binary_search(array, 1, n-2);
if (index != -1):
   print(array[index]);

입력

[7, 8, 9, 12, 10, 6, 3, 2]