Divide & Conquer | Explanation + Visual | [Python]
TLDR(expalanation + visual below code snippet) This problem can be solved by using divide and conquer strategy. We repeatedly divide the problem into subproblem
***TLDR(expalanation + visual below code snippet)*** This problem can be solved by using divide and conquer strategy. We repeatedly divide the problem into subproblems on the basis of whether or not ```arr[low] <= arr[high]``` (whether or not array is sorted) until subporblems become small. Then we solve them directly.  we begin combining solutions to subproblems by taking the minimum of the left and right subproblem solutions.\n\n```python\ndef findMin(self, nums: List[int]) -> int:\n    return self.find_min(nums, 0, len(nums) - 1)\n\t\ndef find_min(self, nums, lo, hi):\n\tif lo >= hi: return nums[lo]\n\tif nums[lo] <= nums[hi]: return nums[lo]\n\tmid = (lo + hi)//2\n\n\tleft = self.find_min(nums, lo, mid)\n\tright = self.find_min(nums, mid + 1, hi)\n\treturn min(left, right);\n\n```\n* * * \n### Divide & Conquer Strategy \n* * * \n\nDivide & Conquer is a strategy for a solving a problem. \n\nWe take a large problem and ***divide*** it into subproblems until the subproblems become ***small*** (we define the meaning of small). Once we have small subproblemsm we can solve them directly because the answer is trivial. Once we start getting solutions to small subproblems we can start to ***combine*** or ***conquer***  these solutions, to get solutions to larger subproblems eventually solving the our intial large problem.  \n\nThis figure denotes a general way to approach ***Divide & Conquer*** \n![image](https://assets.leetcode.com/users/images/d24f02b7-1a45-4899-a908-e5fe584bf29a_1610922746.512331.png)\n\n* * * \n### Why Divide & Conquer ?\n* * * \n\nIn this problem we are given a ***sorted*** array of ***unqiue*** elements that has been rotated and we are asked to find the ***minimum element****. \n\nin general when given a ***sorted array*** and asked to find an element. ***binary search*** is applicable. Binary search is an algorithm that uses the ***divide and conquer*** strategy. \n\nTechnically this array is not perfectly sorted and becuase the array has been rotated. However the relative ordering of the elements is still preserved after rotation.\n\nThus it still may be possible to modify the original binary search algorithm and/or use a ***divide an conquer strategy***.\n\n* * * \n### Applying Divide & Conquer Strategy\n* * * \nwe need to find the minimum in a sorted array that has been rotated zero or more times. \n\nRecall, we say a problem is large when it cannot be solved directly, and the problem is small when it can be solved directly.\n\nWhen the array is sorted, the problem is small because we can solve the problem directly by taking the first element of the array. \n\n![image](https://assets.leetcode.com/users/images/e4ca6343-2e17-4cb6-b3ed-9612a6a7a935_1610931992.3232388.png)\n* * * \nif the array is not completely sorted (in our case rotated 1 or more  times) we cannot solve the problem directly, thus the problem is large. \n\n* * * \n***The question now becomes how do we solve large problems?***\n* * * \n\nObserve a rotated array , notice the relative order of the elements is still preserved leaving sections of the array still sorted. \n\n* * * \n![image](https://assets.leetcode.com/users/images/19285d72-c4f1-491f-8b00-00be7a513840_1610932157.6701047.png)\n\nThe goal is in the example above is to find sorted arrays so we can solve the problem directly. This entire block is not sorted, but if we cut the array in half we are left with 2 sorted pieces.we can solve each peice directly. \n\nin other words if he problem is large (array not sorted) we can divide the problem into subproblems (smaller arrays) until we get small problems (sorted arrrays) and then solve them directly. \n\n![image](https://assets.leetcode.com/users/images/b6d57473-54b0-4d99-b01f-25553a255063_1610932628.1464949.png)\n\nwe know the ***right*** array is sorted because ```arr[4] < arr[6]```so we could solve for the minimum directly \n\nhowever notice the ***left*** array is also sorted because ```arr[0] < arr[3]``` so can also solve directly and we get a minimum of ```4```\n\nour original problem can only have one solution. How do we ensure we choose the correct value? we take the minimum ```min(4, 0) = 0```. in otherwords we combine or conquer subproblems by  taking the minimum of solutions to our subproblems. \n\n* * * \nat each stage we decide if the problem is ***large (not a sorted array)***  if it is ***large***, we break the problem into smaller subproblems (cut the array in half by a midpoint) otherwise the problem is ***small (sorted array***) so we solve the problem ***directly (take first value block of sorted elements)*** when we have found the solution for both the left and right havles of a subproblem we ***combine or conquer*** the solutions ***by taking the minimum of both solutions***.\n\nThis approach becomes clear on a larger example. \n\n![image](https://assets.leetcode.com/users/images/de35a51d-4cd5-49c4-8909-d34f1b23dd37_1610921714.4782262.png)\n\n```python\ndef findMin(self, nums: List[int]) -> int:\n    return self.find_min(nums, 0, len(nums) - 1)\n\t\ndef find_min(self, nums, lo, hi):\n\tif lo >= hi: return nums[lo]\n\tif nums[lo] <= nums[hi]: return nums[lo]\n\tmid = (lo + hi)//2\n\n\tleft = self.find_min(nums, lo, mid)\n\tright = self.find_min(nums, mid + 1, hi)\n\treturn min(left, right)\n```\n\ncode courtesy of [junhaowanggg](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/discuss/582964/4-Solutions-Including-Divide-and-Conquer-Binary-Search-(%2B-Follow-Up))\n\n
['Divide and Conquer', 'Binary Tree']