Note: Leetcode questions moved to github page: https://robinali34.github.io/blog_leetcode/

Template in C++

Binary search on answer

int bs_on_answer(int left, int right) {
    while (left <= right) {
        int pivot = left + (right - left) / 2;
        if (condition(pivot)) {
            right = pivot + 1;
        } else {
            left = pivot + 1;
        }
    }
    return -1;
}

Solution in C++

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            # Subarry on mid's left is sorted
            elif nums[mid] >= nums[left]:
                if target >= nums[left] and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Subarray on mid's right is sorted
            else:
                if target <= nums[right] and target > nums[mid]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

Solution in Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            # Subarry on mid's left is sorted
            elif nums[mid] >= nums[left]:
                if target >= nums[left] and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Subarray on mid's right is sorted
            else:
                if target <= nums[right] and target > nums[mid]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1