Java Solution | Fastest and Easiest solution on the internet!
\'\'\'\n\t\t\n\tclass Solution {\n\t\tpublic int findMin(int[] nums) {\n       \n\t\tint start = 0;\n        int end = nums.length -1;\n        \n            wh
\'\'\'\n\t\t\n\tclass Solution {\n\t\tpublic int findMin(int[] nums) {\n       \n\t\tint start = 0;\n        int end = nums.length -1;\n        \n            while (start <= end) {\n                int mid = start + (end - start)/2;\n\t\t\t\t\n                if (mid < end && nums[mid] > nums[mid + 1])\n                    return nums[mid + 1];     // greater index holds the min element in the array\n                if (start < mid && nums[mid - 1] > nums[mid] )\n                    return nums[mid];     //  greater index holds the min element in the array\n\t\t\t\t\t\n\t\t\t\tif (nums[start] > nums[mid])    // search in the left half \n                    end = mid - 1;\n                else    // search in the right half\n                    start = mid + 1;\n            } \n        return nums[0];\n\t\t}\n\t}\n\'\'\'\t\n*Logic : Return nums[pivot + 1] or return nums[0] if array is sorted.*\n\nTime complexity - O(logn)\nSpace complexity - O(1)\n\n\n1. Apply Binary Search for best time complexity of O(logn).\n2. Find and return nums[pivot + 1]\n3. If no pivot exists, array is sorted, simply return the first element of the array.\n\n\nWhat is this pivot?\nIt is the index where the existing element and the next element do not follow the order of the array, if its ascending then the element at pivot index and pivot + 1 index will be descending and vice versa.\n\nIt is usually the index of the largest element in asc rotated sorted array and index of the smallest number in desc rotated sorted array.\nFor example in\n\'\'\'\n\t\t\n\t\t// rotated asc array\n\t\tarrary1 = {3, 4, 5, 1, 2} \n\t\t// pivot index is 3 where the largest element lies.\n\t\t\n\t\t// rotated desc array\n\t\tarray2 = {7, 6, 10, 9, 8}\n\t\t// pivot index is 1 where the smallest element lies.\n\'\'\'\nConsider a given array\n\'\'\'\n\t\t\t\n\tint arr[] = {4,5,6,7,0,1,2}\n\t// here pivot is the 3rd index\n\t// the minimum element is next the pivot index i.e 4th index and element is 0 which is the minimum\n\tint arr2[] = {1, 2, 3, 4, 5}\n\t// here we do not have a pivot, array is sorted just return the first element i.e. 1 which is the minimum.\n\'\'\'\n\nNow lets find the pivot and return the next element after the pivot index as this will be the minimum element in the array.\n\n4 Cases to find pivot index\n\n\'\'\'\n\t\t\t\n\tif nums[mid] > nums[mid +1]\n\t\treturn nums[mid + 1]; // since nums[pivot + 1] is the minimum element in the array\n\tif nums[mid - 1] > nums[mid]\n\t\treturn nums[mid];\n\tif nums[start] > nums[mid] // search in the left half\n\t\tend = mid - 1;\n\telse // search in the right half\n\t\tstart = mid + 1;\n\'\'\'\n\nWe can solve this question even in linear time, there is no harm in giving it a try.\nNote ** Linear Search vs Binary Search-\n\n**For every million comparisions in linear search there is only 19 comparisions in binary search in worst case senarios. Binary Search is very efficient specially with greater i/p size.**\n\n\'\'\'\n\t\n\tpublic class Main{\n\t\tpublic int findMin(int[] nums) {\n\t\t\t\n\t\t\tfor (int i = 0; i < nums.length; i++) {\n\t\t\t\tif (nums[i] > nums[i+1]) {  // checking for flaws ie different order.\n\t\t\t\t\treturn nums[i+1];     // min element lie after the max element\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn nums[0];     // if array is not rotated\n\t\t}\n\t}\n\t\n\'\'\'\n\n*Logic - Iterate through the array try to find an anomaly and return the i + 1 index which holds the min element in the array.*\nTime Complexity - O(n)\nSpace Complexity - O(1)\n**********************************************\n\nConsider to upvote, if you found it helpful :}**\n\nHappy Coding!!\n\n\n\n
['Binary Tree', 'Java']