logo

TechCodeview

Trobeu el punt bitònic en una seqüència bitònica donada

Et donen a Seqüència Bitònica la tasca és trobar  Punt Bitònic  en ell. Una seqüència bitònica és una seqüència de nombres que és la primera estrictament augmentant després després d'un punt estrictament decreixent .
Un punt bitònic és un punt de la seqüència bitònica abans del qual els elements augmenten estrictament i després del qual els elements són estrictament decreixents.
Nota:- La seqüència donada sempre serà una seqüència bitònica vàlida.
Exemples:  

Entrada: arr[] = {8 10 100 200 400 500 3 2 1}
Sortida : 500

Entrada: arr[] = {10 20 30 40 30 20}
Sortida : 40

Entrada : arr[] = {60 70 120 100 80}
Sortida: 120

Taula de continguts



[Enfocament ingenu] Ús de la cerca lineal: O(n) Temps i O(1) Espai

Un enfocament senzill és iterar a través de la matriu i fer-ne un seguiment màxim element ocorregut fins ara. un cop finalitzat el recorregut retorneu l'element màxim.

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 
// 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# 
// 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));

Sortida 
500

[Enfocament esperat] Ús de la cerca binària: temps O(logn) i espai O(1).

La matriu d'entrada segueix a patró monòton . Si un element ho és més petit que la següent es troba a la i segment creixent de la matriu i l'element màxim definitivament existiran després d'ella. A la inversa si un element ho és més gran que la següent es troba a la segment decreixent és a dir, el màxim és en aquesta posició o abans. Per tant podem utilitzar cerca binària per trobar de manera eficient l'element màxim de la matriu.


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 
// 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# 
// 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));

Sortida 
500
Crea un qüestionari