주어진 바이토닉 시퀀스에서 바이토닉 포인트 찾기

당신은 주어진 바이토닉 시퀀스 임무는 찾는 것이다 바이토닉 포인트 그 안에. 바이토닉 시퀀스(Bitonic Sequence)는 엄격하게 첫 번째 숫자의 시퀀스입니다. 증가 그런 다음 엄격하게 한 지점 후에 감소하는 .
바이토닉 포인트(Bitonic Point)는 이전에 요소가 엄격하게 증가하고 이후에 요소가 엄격하게 감소하는 바이토닉 시퀀스의 지점입니다.
참고:- 주어진 시퀀스는 항상 유효한 바이토닉 시퀀스입니다.
예:

입력: 도착[] = {8 10 100 200 400 500 3 2 1}
산출 : 500

입력: 도착[] = {10 20 30 40 30 20}
산출 : 40

입력 : arr[] = {60 70 120 100 80}
산출: 120

[순진한 접근 방식] 선형 검색 사용 - O(n) 시간 및 O(1) 공간
[예상 접근 방식] 이진 검색을 활용 - O(logn) 시간과 O(1) 공간

[순진한 접근 방식] 선형 검색 사용 - O(n) 시간 및 O(1) 공간

간단한 접근 방식은 배열을 반복하고 최고 요소가 지금까지 발생했습니다. 순회가 완료되면 최대 요소를 반환합니다.

C++

// C++ program to find maximum element in bitonic // array using linear search #include    #include  using namespace std; int bitonicPoint(vector<int> &arr) {  int res = arr[0];     // Traverse the array to find   // the maximum element  for (int i = 1; i < arr.size(); i++)   res = max(res arr[i]);    return res;  } int main() {  vector<int> arr = {8 10 100 400 500 3 2 1};  cout << bitonicPoint(arr);   return 0;  }

// C program to find maximum element in bitonic // array using linear search #include  int bitonicPoint(int arr[] int n) {  int res = arr[0];  // Traverse the array to find   // the maximum element  for (int i = 1; i < n; i++)   res = (res > arr[i]) ? res : arr[i];  return res; } int main() {  int arr[] = {8 10 100 400 500 3 2 1};  int n = sizeof(arr) / sizeof(arr[0]);  printf('%dn' bitonicPoint(arr n));   return 0; }

Java

// Java program to find maximum element in bitonic // array using linear search import java.util.Arrays; class GfG {  static int bitonicPoint(int[] arr) {  int res = arr[0];  // Traverse the array to find   // the maximum element  for (int i = 1; i < arr.length; i++)   res = Math.max(res arr[i]);  return res;  }  public static void main(String[] args) {  int[] arr = {8 10 100 400 500 3 2 1};  System.out.println(bitonicPoint(arr));  } }

Python

# Python program to find maximum element in  # bitonic array using linear search def bitonicPoint(arr): res = arr[0] # Traverse the array to find  # the maximum element for i in range(1 len(arr)): res = max(res arr[i]) return res if __name__ == '__main__': arr = [8 10 100 400 500 3 2 1] print(bitonicPoint(arr))

// C# program to find maximum element in bitonic // array using linear search using System; class GfG {  static int bitonicPoint(int[] arr) {  int res = arr[0];  // Traverse the array to find   // the maximum element  for (int i = 1; i < arr.Length; i++)   res = Math.Max(res arr[i]);  return res;  }  static void Main() {  int[] arr = {8 10 100 400 500 3 2 1};  Console.WriteLine(bitonicPoint(arr));  } }

JavaScript

// JavaScript program to find maximum element in  // bitonic array using linear search function bitonicPoint(arr) {  let res = arr[0];  // Traverse the array to find   // the maximum element  for (let i = 1; i < arr.length; i++)   res = Math.max(res arr[i]);    return res; } const arr = [8 10 100 400 500 3 2 1]; console.log(bitonicPoint(arr));

산출

[예상 접근 방식] 이진 검색을 활용 - O(logn) 시간과 O(1) 공간

입력 배열은 다음을 따릅니다. 단조로운 패턴 . 요소가 다음과 같은 경우 더 작은 다음 것보다 그것은 i에 있다 세그먼트 증가 배열의 최대 요소는 확실히 그 뒤에 존재할 것입니다. 반대로 요소가 보다 큰 다음 것보다 감소하는 세그먼트 이는 최대값이 이 위치 또는 이전 위치에 있음을 의미합니다. 그러므로 우리는 사용할 수 있습니다 이진 검색 배열에서 최대 요소를 효율적으로 찾습니다.

C++

// C++ program to find the maximum element in a bitonic  // array using binary search. #include    #include  using namespace std; int bitonicPoint(vector<int> &arr) {  int n = arr.size();    // Search space for binary search.  int lo = 0 hi = n - 1;   int res = n - 1;     while(lo <= hi) {  int mid = (lo + hi) / 2;     // Decreasing segment  if(mid + 1 < n && arr[mid] > arr[mid + 1]) {  res = mid;   hi = mid - 1;   }    // Increasing segment  else {  lo = mid + 1;   }  }    return arr[res];  }  int main() {  vector<int> arr = {8 10 100 400 500 3 2 1};   cout << bitonicPoint(arr);   return 0;  }

// C program to find the maximum element in a bitonic  // array using binary search. #include  int bitonicPoint(int arr[] int n) {    // Search space for binary search.  int lo = 0 hi = n - 1;   int res = hi;     while(lo <= hi) {  int mid = (lo + hi) / 2;     // Decreasing segment  if(mid + 1 < n && arr[mid] > arr[mid + 1]) {  res = mid;   hi = mid - 1;   }  // Increasing segment  else {  lo = mid + 1;   }  }    return arr[res];  }  int main() {  int arr[] = {8 10 100 400 500 3 2 1};   int n = sizeof(arr) / sizeof(arr[0]);   printf('%dn' bitonicPoint(arr n));   return 0;  }

Java

// Java program to find the maximum element in a bitonic  // array using binary search. import java.util.Arrays; class GfG {  static int bitonicPoint(int[] arr) {  int n = arr.length;    // Search space for binary search.  int lo = 0 hi = n - 1;   int res = n - 1;     while (lo <= hi) {  int mid = (lo + hi) / 2;     // Decreasing segment  if (mid + 1 < n && arr[mid] > arr[mid + 1]) {  res = mid;   hi = mid - 1;   }  // Increasing segment  else {  lo = mid + 1;   }  }    return arr[res];   }  public static void main(String[] args) {  int[] arr = {8 10 100 400 500 3 2 1};   System.out.println(bitonicPoint(arr));   } }

Python

# Python program to find the maximum element in a bitonic  # array using binary search. def bitonicPoint(arr): # Search space for binary search. lo = 0 hi = len(arr) - 1 res = hi while lo <= hi: mid = (lo + hi) // 2 # Decreasing segment if mid + 1 < len(arr) and arr[mid] > arr[mid + 1]: res = mid hi = mid - 1 # Increasing segment else: lo = mid + 1 return arr[res] if __name__ == '__main__': arr = [8 10 100 400 500 3 2 1] print(bitonicPoint(arr))

// C# program to find the maximum element in a bitonic  // array using binary search. using System; class GfG {  static int bitonicPoint(int[] arr) {  int n = arr.Length;    // Search space for binary search.  int lo = 0 hi = n - 1;   int res = n - 1;     while (lo <= hi) {  int mid = (lo + hi) / 2;     // Decreasing segment  if (mid + 1 < n && arr[mid] > arr[mid + 1]) {  res = mid;   hi = mid - 1;   }  // Increasing segment  else {  lo = mid + 1;   }  }    return arr[res];   }  static void Main() {  int[] arr = {8 10 100 400 500 3 2 1};   Console.WriteLine(bitonicPoint(arr));   } }

JavaScript

// JavaScript program to find the maximum element in a bitonic  // array using binary search. function bitonicPoint(arr) {  const n = arr.length;    // Search space for binary search.  let lo = 0 hi = n - 1;   let res = n - 1;     while (lo <= hi) {  let mid = Math.floor((lo + hi) / 2);     // Decreasing segment  if (mid + 1 < n && arr[mid] > arr[mid + 1]) {  res = mid;   hi = mid - 1;   }  // Increasing segment  else {  lo = mid + 1;   }  }    return arr[res];  } const arr = [8 10 100 400 500 3 2 1];  console.log(bitonicPoint(arr));

산출

퀴즈 만들기