Divide-and-Conquer

tags: Binary Search,LeetCodeNJ YouTube: https://www.youtube.com/watch?v=LPFhl65R7ww The most difficult thing is doing binary search among two sorted arrays, in this video Tushar Roy given us a straightforward method of how to do binary search among tow sorted arrays. Assume we have two sorted arrays, X and Y, and cut them between at x2,x3 and y3,y4: If we meet the conditions: x2 <= y3 y2 <= x3 then we find the median postion, as the merged arrays of the four elements may be order by:...

tags: Binary Search,LeetCode101 There is three corner cases must be handled if we don’t find target in nums: Return r + 1 if target is greater than right. Or return mid + 1 if target is greater than mid. Otherwise return mid. class Solution { public: int searchInsert(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; int mid = r / 2; while (l !...

tags: Divide-and-Conquer,LeetCode101,Binary Search class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { int n = matrix.size(); int m = matrix[0].size(); int l = 0, r = m * n - 1; while (l != r){ int mid = l + (r - l) / 2; if (matrix[mid / m][mid % m] < target) l = mid + 1; else r = mid; } return matrix[r / m][r % m] == target; } };