logo

TechCodeview

Keresse meg a bitonikus pontot az adott bitonikus sorozatban

Megkapod a Biton szekvencia a feladat megtalálni  Bitonikus pont  benne. A bitonikus sorozat olyan számsorozat, amely szigorúan az első növekvő majd egy pont után szigorúan csökkenő .
A bitonikus pont egy olyan pont a bitonikus sorrendben, amely előtt az elemek szigorúan növekednek, és amely után az elemek szigorúan csökkennek.
Megjegyzés: - Az adott szekvencia mindig érvényes bitonikus szekvencia lesz.
Példák:  

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

Bemenet: arr[] = {10 20 30 40 30 20}
Kimenet : 40

Bemenet : arr[] = {60 70 120 100 80}
Kimenet: 120

Tartalomjegyzék



[Naiv megközelítés] Lineáris keresés használata - O(n) idő és O(1) tér

Egy egyszerű megközelítés a tömb iterációja, és nyomon követése a maximális elem történt eddig. ha a bejárás befejeződött, adja vissza a maximális elemet.

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

Kimenet 
500

[Elvárt megközelítés] Bináris keresés használata – O(logn) idő és O(1) tér

A bemeneti tömb követi a monoton minta . Ha egy elem az kisebb mint a következőben az i-ben fekszik növekvő szegmens a tömbből és a maximális elem biztosan létezni fog utána. Fordítva, ha egy elem nagyobb mint a következőben rejlik a csökkenő szegmens vagyis a maximum vagy ennél a pozíciónál van, vagy korábban. Ezért használhatjuk bináris keresés hogy hatékonyan megtaláljuk a tömb maximális elemét.


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

Kimenet 
500
Kvíz létrehozása