Algorithm Notes: Binary Search

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        f = [0] * (n + 1)
        f[0] = 0
        f[1] = 1
        for i in range(2, n + 1):
            f[i] = f[i - 1] + f[i - 2]
        
        return f[n]
        

class Solution:
    """
    @param nums: The integer array.
    @param target: Target to find.
    @return: The first position of target. Position starts from 0.
    """
    def binarySearch(self, nums, target):
        # write your code here
        if not nums:
            return -1
            
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            
            mid = int((start + end) / 2)
        
            if nums[mid] == target:
                ### since we are looking for first, so update end, search in left part, including mid!
                end = mid
            
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
                
        ### out the loop, leave start, end, start + 1 = end:
        #since we are looking for first, so we should check the left part first:
        if nums[start] == target:
            return start
        
        if nums[end] == target:
            return end
        
        return -1

class Solution:
    """
    @param nums: An integer array sorted in ascending order
    @param target: An integer
    @return: An integer
    """
    def lastPosition(self, nums, target):
        # write your code here
        if not nums:
            return -1
        
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = int((start + end) / 2)
            
            if nums[mid] == target:
                ### search last part, so including current mid, and search in right half:
                start = mid
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        
        ### out the loop, we should have start + 1 = end:
        ### check end first since looking for last position
        if nums[end] == target:
            return end
        
        if nums[start] == target:
            return start
        
        return - 1
 

class Solution:
    """
    @param reader: An instance of ArrayReader.
    @param target: An integer
    @return: An integer which is the first index of target.
    """
    def searchBigSortedArray(self, reader, target):
        # write your code here
        if not reader:
            return -1
        
        ###  这题的特点是数组假设无穷大。所以没有确定的右端点。
        ### 那么如何在logK 的时间复杂度找到target呢？
        ### 需要使用倍增法。
        
        ### 倍增
        kth = 1
        while reader.get(kth - 1) < target:
            kth = kth * 2
        
        ### now we found the right side larger than target, kth - 1 as the right
        ### 那么找到left 和 right， 对此区间再进行二分查找就可以了。
        left = kth // 2 - 1
        right = kth - 1
        while left + 1 < right:
            mid = int((left + right) / 2)
            
            if reader.get(mid) == target:
                right = mid
                
            elif reader.get(mid) < target:
                left = mid + 1
            else:
                right = mid - 1
            
        if reader.get(left) == target:
            return left 
        
        if reader.get(right) == target:
            return right
            
        return -1
        

class Solution:
    """
    @param nums: a mountain sequence which increase firstly and then decrease
    @return: then mountain top
    """
    def mountainSequence(self, nums):
        if not nums:
            return -1
            
        # find first index i so that nums[i] > nums[i + 1]
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            # mid + 1 保证不会越界
            # 因为 start 和 end 是 start + 1 < end
            if nums[mid] > nums[mid + 1]:
                end = mid
            else:
                start = mid
        
        return max(nums[start], nums[end])

class Solution:
    def search(self, A, target):
        if not A:
            return -1
 
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if A[mid] >= A[start]:
                if A[start] <= target <= A[mid]:
                    end = mid
                else:
                    start = mid
            else:
                if A[mid] <= target <= A[end]:
                    start = mid
                else:
                    end = mid
                    
        if A[start] == target:
            return start
        if A[end] == target:
            return end
        return -1
        

class Solution:
    def findPeakElement(self, nums):
        ### return any peak
        ### Binary Search
        ### 1 2 1 3 5 6 4
        ### S     M     E
        ### since num[-1] is negative infinity
        ### if we have  nums[mid - 1] < nums[mid], we know there must be a peak at [mid, :]
        ### otherwise, peak should be contained in left part
        if not nums:
            return None
        
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = int((start + end) / 2)
            if nums[mid - 1] < nums[mid]:
                start = mid
            else:
                end = mid
        
        if nums[start] > nums[end]:
            return start
        else:
            return end

class Solution:
    """
    @param L: Given n pieces of wood with length L[i]
    @param k: An integer
    @return: The maximum length of the small pieces
    """
    def woodCut(self, L, k):
        # write your code here
        if not L:
            return 0
            
        max_len = int(sum(L) / k)
        min_len = int(min(L) / k)
        start, end = min_len, max_len
        
        if end <= 1:
            return end
 
        while start + 1 < end:
            mid = int((start + end) / 2)
            # 长度为mid时能够切出的段数如果大于等于k
            # 把mid作为起点开始新的搜索
            if self.count_k(mid, L) >= k:
                start = mid 
            else:
                end = mid - 1
 
        if self.count_k(end, L) >= k:
            return end
        if self.count_k(start, L) >= k:
            return start
 
        return 0
        
    def count_k(self, mid, L):
        k_size = 0
        for l in L:
            k_size += l // mid
        return k_size
        
 

class Solution:
    def minArea(self, image, x, y):
        if not image or not image[0]:
            return 0
        
        n, m = len(image), len(image[0])
        left = self.find_first(image, 0, y, self.check_column)
        right = self.find_last(image,y, m - 1, self.check_column)
        up = self.find_first(image, 0, x, self.check_row)
        down = self.find_last(image, x, n - 1, self.check_row)
        
        return (right - left + 1) * (down - up + 1)
        
    ### 通过四个二分完成
    ### https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/solution/
    
    def find_first(self, image, start, end, check_func):
        while start + 1 < end:
            mid = int((start + end) / 2)
            if check_func(image, mid):
                end = mid
            else:
                start = mid
        if check_func(image, start):
            return start
        return end
 
    def find_last(self, image, start, end, check_func):
        while start + 1 < end:
            mid = int((start + end) / 2)
            if check_func(image, mid):
                start = mid
            else:
                end = mid
        if check_func(image, end):
            return end
        return start
 
    def check_column(self, image, col):
        for i in range(len(image)):
            if image[i][col] == '1':
                return True
        return False
 
    def check_row(self, image, row):
        for j in range(len(image[0])):
            if image[row][j] == '1':
                return True
        return False
        

### 以下为可通过的解法: Binary Search, DP
 
class Solution:
    """
    @param pages: an array of integers
    @param k: An integer
    @return: an integer
    """
    def copyBooks(self, pages, k):
        n = len(pages)
        if n == 0:
            return 0
        l = max(pages)
        r = sum(pages)
        while l < r:
            mid = (l + r) // 2
            if self.ok(pages, k, mid):
                r = mid
            else:
                l = mid + 1 
        return l
 
    def ok(self, pages, k, tm):
        num = 1
        pageSum = 0
        for i in pages:
            if pageSum + i <= tm:
                pageSum += i 
            else:
                num += 1  
                pageSum = i
        return num <= k
 
# DP
class Solution:
    """
    @param pages: an array of integers
    @param k: An integer
    @return: an integer
    """
 
    def copyBooks(self, pages, k):
        n = len(pages)
        if k > n:
            k = n
 
        if n == 0:
            return 0
 
        sum = [0] * n
        sum[0] = pages[0]
        for i in range(1, n):
            sum[i] = sum[i - 1] + pages[i]
 
        f = [[0] * k for _ in range(n)]
 
        for i in range(n):
            f[i][0] = sum[i]
 
        for j in range(1, k):
            p = 0
            f[0][j] = pages[0]
            for i in range(1, j):
                f[i][j] = max(f[i - 1][j], pages[i])
 
            for i in range(j, n):
                while (p < i and f[p][j - 1] < sum[i] - sum[p]):
                    p += 1
                f[i][j] = max(f[p][j - 1], sum[i] - sum[p])
                if p > 0:
                    p -= 1
                f[i][j] = min(f[i][j], max(f[p][j - 1], sum[i] - sum[p]))
        return f[n-1][k-1]
 
 
### My DP solution: Time limit Exceeded
 
class Solution:
    """
    @param pages: an array of integers
    @param k: An integer
    @return: an integer
    """
    def copyBooks(self, pages, k):
        # write your code here
        # 划分型动态规划
        
        # 有点类似greedy的思路
        
        # 需要找到一种分段方式， 分成不超过k段，考虑到可能有人没有workload，使得所有段的数字之和，的最大值， 最小。
        
        
        # last person (Kth person) on pages[j], pages[j+1] ... pages[n - 1] , j = 0, 1, 2,...,i - 1, i is from {n}
        # K-1 previous persons distributed on pages[0]...pages[j - 1]
        
        n = len(pages)
        if not pages or n == 0 or k == 0:
            return 0
        
        ### 考虑 k> n
        
        if k > n:
            k = n
 
        
        MAX = float('Inf')
        f = [[MAX] * (n + 1) for _ in range(k + 1)]
        f[0][0] = 0
        for i in range(1, k + 1):
            f[i][0] = 0
 
            
        for t in range(1, k + 1):
            for i in range(1, n + 1):
                temp = 0
                for j in range(i, -1, -1):
                    # temp  = A[j] + ... + A[i - 1 ]
                    if f[t - 1][j] != MAX:
                        f[t][i] = min(f[t][i], max(f[t - 1][j], temp))
                    # update temp
                    if j > 0:
                        temp += pages[j - 1]
                    
                    # 此处剪枝
                    if f[t][i] < temp:
                        break
        return f[k][n]

class Solution:
    """
    @param a: the given number
    @param b: another number
    @return: the greatest common divisor of two numbers
    """
    def gcd(self, a, b):
        # write your code here
        if a > b:
            small = b
            big = a
        else:
            small = a
            big = b
        
        if small != 0:
            return self.gcd(small, big % small)
        else:
            return big

class Solution:
    """
    @param A: An integer array.
    @param B: An integer array.
    @return: a double whose format is *.5 or *.0
    """
    def findMedianSortedArrays(self, A, B):
        n = len(A) + len(B)
        if n % 2 == 1:
            return self.findKth(A, 0, B, 0, n // 2 + 1)
        else:
            smaller = self.findKth(A, 0, B, 0, n // 2)
            bigger = self.findKth(A, 0, B, 0, n // 2 + 1)
            return (smaller + bigger) / 2
 
    def findKth(self, A, index_a, B, index_b, k):
        if len(A) == index_a:
            return B[index_b  + k - 1]
        if len(B) == index_b:
            return A[index_a + k - 1]
        if k == 1:
            return min(A[index_a], B[index_b])
        
        a = A[index_a + k // 2 - 1] if index_a + k // 2 <= len(A) else None
        b = B[index_b + k // 2 - 1] if index_b + k // 2 <= len(B) else None
        
        if b is None or (a is not None and a < b):
            return self.findKth(A, index_a + k // 2, B, index_b, k - k // 2)
        return self.findKth(A, index_a, B, index_b + k // 2, k - k // 2)
 

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        #get overall sense:
        a = len(nums1)
        b = len(nums2)
        length = a+b
        # found the total size of the "merged" array
        # now define them short, long, based on their length
        # notice that:
        # short and long will contribute a portion to the merged array left side before the median, we need to find out the location that happend in short, and long. 
        # For example:
        # short: 1,3,4
        # long : 2,5,9,10
        # mergerd: 1,(2),3,4,(5),(9),(10)
        # here we have: median happened at index = 3 <== (3+5)/2 = 4th number, as the median number, thus
        # including the median number, the left has a total of 4 numbers, three are from short, only one is from long.
        # to find out the "three" and "one", which are the numbers contributed from both long, and short, we could easily identify the median number of the merged array.
        # so we do the following to ensure that we are operating on the short and long lists by redefining them:
        
        if a > b:
            short = b
            short_v = nums2
            long = a
            long_v = nums1
            imax = b
        else:
            short = a
            short_v = nums1
            long = b
            long_v = nums2
            imax = a
            
        imin = 0
        
        if long == 0:
            raise ValueError
          
        median_index = (length+1) // 2 
        
        #let us define ptrs imin, imax, 
        # recall the example, short, long
        # consider the imin, and imax are searched range for i ptr, on the short array:
        # thus, imin starts at 0, imax starts from the end of short array.
        # thus, imin = 0, imax = len(short) at the begining.
        # performing the binary search on the short array, we could narrow down the imin, imax range, adn finally locate the i index at short, so that we could know j index at long, both numbers including ith, jth in short and long, contributed towards the left part of the merged array.
        
        #binary search:
        while imin <= imax:
            # binary search guess i happen at the middle
            i = (imin+imax) // 2
            # derive j, according to i, known that how many numbers should exist in left
            j = median_index - i
            # validate the guess and iterate
            # if the i does not exceed the short, and the long last contributed is larger than the next remaining of the short, meaning the long contributed last one should not count, but should be the shor16. 
 
            elif i> 0 and short_v[i-1] > long_v[j]:
                imax = i-1
                
            #eventually, we should have the perfect i, that indicated short contributed i numbers, long contributed j numbers, the last contirbuted short number is smaller than the remining of the long. and long's last contributed number is also smaller than the short remaining next number.
            
            else:
            # we need consider several cases when i, or j could be zero, otherwise, the max left will be the maximum between each long and short contributed last number
                if i == 0: max_left = long_v[j-1]
                elif j == 0: max_left = short_v[i-1]
                else: max_left = max(long_v[j-1],short_v[i-1])
                
                # if the merged size is odd, the max_left is the single number, which should be the last number of left part
                if (length) % 2 == 1:
                    return max_left
                
                # we also need to consider when all short or all long contributed, as well as when the merged size is even:
                if i == short: min_right = long_v[j]
                elif j == long: min_right = short_v[i]
                #then the min_right is the minimum between the long remaining next and short remaining next
                else: min_right = min(long_v[j], short_v[i])
                #return the median calculation from left and right. 
                return(max_left+min_right) /2.0

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        # write your code here
        start, end = 1, n
        while start + 1 < end:
            mid = int((start + end) / 2)
            if isBadVersion(mid):
                end = mid
            else:
                start = mid + 1
        if isBadVersion(start):
            return start
        return end
        

class Solution:
    """
    @param nums: The integer array.
    @param target: Target to find.
    @return: The first position of target. Position starts from 0.
    """
    def binarySearch(self, nums, target):
        # write your code here
        if not nums:
            return -1
            
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            
            mid = int((start + end) / 2)
        
            if nums[mid] == target:
                ### since we are looking for first, so update end, search in left part, including mid!
                end = mid
            
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
                
        ### out the loop, leave start, end, start + 1 = end:
        #since we are looking for first, so we should check the left part first:
        if nums[start] == target:
            return start
        
        if nums[end] == target:
            return end
        
        return -1

class Solution:
    """
    @param nums: An integer array sorted in ascending order
    @param target: An integer
    @return: An integer
    """
    def lastPosition(self, nums, target):
        # write your code here
        if not nums:
            return -1
        
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = int((start + end) / 2)
            
            if nums[mid] == target:
                ### search last part, so including current mid, and search in right half:
                start = mid
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        
        ### out the loop, we should have start + 1 = end:
        ### check end first since looking for last position
        if nums[end] == target:
            return end
        
        if nums[start] == target:
            return start
        
        return - 1
 

class Solution:
    def searchRange(self, nums, target):
        if not nums:
            return [-1, -1]
        return [self.searchFirst(nums, target), self.searchLast(nums, target)]
 
    
    def searchFirst(self, nums, target):
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = int((start + end) / 2)
            if nums[mid] == target:
                end = mid
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1
    def searchLast(self, nums, target):
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = int((start + end) / 2)
            if nums[mid] == target:
                start = mid
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
                
        if nums[end] == target:
            return end
        if nums[start] == target:
            return start
 
        return -1
 

class Solution:
    """
    @param nums: a mountain sequence which increase firstly and then decrease
    @return: then mountain top
    """
    def mountainSequence(self, nums):
        if not nums:
            return -1
            
        # find first index i so that nums[i] > nums[i + 1]
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            # mid + 1 保证不会越界
            # 因为 start 和 end 是 start + 1 < end
            if nums[mid] > nums[mid + 1]:
                end = mid
            else:
                start = mid
        
        return max(nums[start], nums[end])

class Solution:
    def peakIndexInMountainArray(self, nums: List[int]) -> int:
        if not nums:
            return -1
    
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = int((start + end) / 2)
            
            if nums[mid] > nums[mid + 1]:
                end = mid
            else:
                start = mid
        
        if nums[start] >= nums[end]:
            return start
        else:
            return end

class Solution:
    """
    @param nums: An integer array
    @return: nothing
    """
    def recoverRotatedSortedArray(self, nums):
        # write your code here
        minIndex = self.findCut(nums)
        print(minIndex)
        if minIndex == 0:
            return
        
        start, end = 0, len(nums) - 1 
        self.rotateArray(nums, start, minIndex - 1)
        self.rotateArray(nums, minIndex, end)
        self.rotateArray(nums, start, end)
    
    
    def findCut(self, nums):
        if nums is None or len(nums) < 2:
            return 0
            
        start, end = 0, len(nums) - 1
    
        while start + 1< end:
            mid = int((start + end) / 2)
            if nums[mid] > nums[end]:
                start = mid + 1
            elif nums[mid] < nums[end]:
                end = mid
            else:
                end -= 1
        if nums[start] > nums[end]:
    
            return end
        else:
            return start
    
    def rotateArray(self, nums, left, right):
        while left <= right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1 
            right -= 1

### Binary Search ! 此题注意处理矩阵坐标的小技巧。
class Solution:
    def searchMatrix(self, matrix, target):
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
 
        start, end = 0, n*m - 1
        while start + 1 < end:
            mid = int((start + end) / 2)
            pivot = matrix[mid // n][mid % n]
            if pivot == target:
                return True
            else:
                if target < pivot:
                    end = mid - 1
                else:
                    start = mid + 1
        if matrix[start // n][start % n] == target or matrix[end // n][end % n] == target:
            return True
                    
        return False
 

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        ### start from the top-right corner:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
        
        x, y = 0, n - 1
        
        while x <= m - 1 and y >= 0:
            if matrix[x][y] == target:
                return True
            elif matrix[x][y] < target:
                x += 1
            else:
                y -= 1
        
        return False

class Solution:
    """
    @param a: the given number
    @param b: another number
    @return: the greatest common divisor of two numbers
    """
    def gcd(self, a, b):
        # write your code here
        if a > b:
            small = b
            big = a
        else:
            small = a
            big = b
        
        if small != 0:
            return self.gcd(small, big % small)
        else:
            return big

class Solution:
    def myPow(self, x, n):
        ### 矩阵快速幂
        ### 计算x的n次方，即x^n
        ### x^n = x^(n/2) * x^(n/2)
        ### So a O(n) problem can be transferred to a O(logn) Problem.
        if n == 0:
            return 1
        if n < 0:
            temp =  1 / self.myPow(x, -n // 2)
            if n % 2 == 0:
                return temp * temp
            else:
                return temp * temp * 1/x
        else:
            temp = self.myPow(x, n // 2)
            if n % 2 == 0:
                return temp * temp
            else:
                return temp * temp * x