logo

TechCodeview

Find bitonisk punkt i en given bitonisk rækkefølge

Du får en Bitonisk sekvens opgaven er at finde  Bitonic punkt  i den. En bitonisk sekvens er en sekvens af tal, som først er strengt taget stigende derefter efter et punkt strengt taget faldende .
Et bitonisk punkt er et punkt i bitonisk rækkefølge, før hvilket elementer er strengt stigende, og hvorefter elementer er strengt faldende.
Bemærk:- Given Sequence vil altid være en gyldig bitonisk sekvens.
Eksempler:  

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

Input: arr[] = {10 20 30 40 30 20}
Produktion : 40

Input : arr[] = {60 70 120 100 80}
Produktion: 120

Indholdsfortegnelse



[Naiv tilgang] Brug af lineær søgning - O(n) tid og O(1) mellemrum

En simpel tilgang er at iterere gennem arrayet og holde styr på maksimum element forekommet indtil videre. når gennemgangen er fuldført returnerer det maksimale element.

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

Produktion 
500

[Forventet tilgang] Brug af binær søgning - O(logn) Tid og O(1) Mellemrum

Input-arrayet følger a monotont mønster . Hvis et element er mindre end den næste ligger den i i'et stigende segment af arrayet og det maksimale element vil helt sikkert eksistere efter det. Omvendt hvis et element er større end den næste den ligger i faldende segment hvilket betyder, at maksimum er enten ved denne position eller tidligere. Derfor kan vi bruge binær søgning for effektivt at finde det maksimale element i arrayet.


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

Produktion 
500
Opret quiz