ניתן לך א רצף ביטוני המשימה היא למצוא נקודה ביטונית בּוֹ. רצף ביטוני הוא רצף של מספרים שהוא ראשון למהדרין גָדֵל ואז אחרי נקודה למהדרין פּוֹחֵת .
נקודה ביטונית היא נקודה ברצף ביטוני שלפניה האלמנטים גדלים בהחלט ואחריה האלמנטים הולכים ופוחתים.
הערה: רצף נתון תמיד יהיה רצף ביטוני חוקי.
דוגמאות:
קֶלֶט: arr[] = {8 10 100 200 400 500 3 2 1}
תְפוּקָה : 500
קֶלֶט: arr[] = {10 20 30 40 30 20}
תְפוּקָה : 40
קֶלֶט : arr[] = {60 70 120 100 80}
תְפוּקָה: 120
תוכן עניינים
- [גישה נאיבית] שימוש בחיפוש לינארי - O(n) זמן ו-O(1) Space
- [גישה צפויה] שימוש בחיפוש בינארי - O(logn) זמן ו-O(1) Space
[גישה נאיבית] שימוש בחיפוש לינארי - O(n) זמן ו-O(1) Space
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));
תְפוּקָה
500
[גישה צפויה] שימוש בחיפוש בינארי - O(logn) זמן ו-O(1) Space
מערך הקלט עוקב אחרי א דפוס מונוטוני . אם אלמנט הוא קטן יותר מאשר הבא הוא נמצא ב-i קטע הולך וגדל של המערך והאלמנט המקסימלי בהחלט יתקיים אחריו. לעומת זאת אם אלמנט הוא גדול יותר מאשר הבא הוא טמון ב קטע יורד כלומר המקסימום נמצא במיקום זה או מוקדם יותר. לכן אנחנו יכולים להשתמש חיפוש בינארי כדי למצוא ביעילות את האלמנט המקסימלי במערך.
// 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));
תְפוּקָה
500צור חידון