LC 278 & LC 374 & LC 704 & LC 852

Solution to LeetCode 278 First Bad Version, LeetCode 374 Guess Number Higher or Lower, LeetCode 704 Binary Search, and LeetCode 852 Peak Index in a Mountain Array.

LeetCode 278

First Bad Version (Easy) [link]

Find the smallest index of items such that it is a bad version. firstBadVersion returns the first index that isBadVersion is true.

If m is the bad version then search backwards, else search forwards.

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l = 0
        r = n
        while l < r:
            m = l + (r - l) // 2
            if isBadVersion(m):
                r = m
            else:
                l = m + 1
        return l

LeetCode 374

Guess Number Higher or Lower (Easy) [link]

Time complexity O(log n), space complexity O(1).

class Solution:
    def guessNumber(self, n: int) -> int:
        l = 0
        r = n
        while l < r:
            m = l + (r - l) // 2
            # if guess(m) == 0:
            #     return m
            if guess(m) <= 0:
                r = m
            else:
                l = m + 1
        return l

LeetCode 704

Binary Search (Easy) [link]

Time complexity O(log n), space complexity O(1).

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)
        while l < r:
            m = l + (r-l) // 2
            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m 
            else:
                l = m + 1
        return -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1
        while l <= r:
            m = l + (r-l) // 2
            if nums[m] == target:
                return m
            elif nums[m] >= target:
                r = m - 1
            else:
                l = m + 1
        return -1

LeetCode 852

Peak Index in a Mountain Array (Easy) [link]

Time complexity O(log n), space complexity O(1).

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l = 0
        r = len(arr)
        while l < r:
            m = r + (l - r) //2 
            if arr[m] > arr[m+1]:
                r = m
            else:
                l = m + 1
        return l