BinarySearch 0895 Complete an Arithmetic Sequence

Problem statement

https://binarysearch.com/problems/Complete-an-Arithmetic-Sequence/

Solution

Equal to Leetcode 1228 Missing Number In Arithmetic Progression.

Complexity

It is O(log n) for time and O(1) for space.

Code

class Solution:
    def solve(self, arr):
        diff = (arr[-1] - arr[0])//(len(arr))
        beg, end = 0, len(arr) - 1
        while beg < end:
            mid = (beg + end)//2
            if arr[mid] == arr[0] + mid*diff:
                beg = mid + 1
            else:
                end = mid
                
        return arr[0] + diff * beg