Binary Search problems summary

In Leetcode Binary Search problems, it provide better search O(log n) instead of O(n) regular search.

[ basically, steps are ]

1. determine low and high starting value
2. set mid equal (low + high) / 2
2. give a while loop when low < high
3. return target value if found else increase low or reduce high's value base on mid

[ why those steps ]


first, it's important to know the range we are going to search.
then we can choose the middle element
compare list[mid] with target and then adjust low or high.

Said you want to find 83 in a list from [1,2,...,100], you only need log2 100 ~= 6.6 times search which much better than 100 times, right?


[ 153. Find Minimum in Rotated Sorted Array ]

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

1.low = 0 , high = length of list - 1

2.think about two rotated case,

[2,3,1] and [3,1,2], both list[low] larger than list[high]

 we can use it as condition for the while loop

3. if list[mid] > list[high], it mean something like [2,3,1] and minimum value on the right part of middle.

Time complexity:  O(log n). 
Space complexity: O(1). 

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 0
        high = len(nums) - 1
        while low < high and nums[low] > nums[high]:
            mid = (low + high) / 2
            if nums[mid] > nums[high]:
                low = mid + 1
            else:
                high = mid
        return nums[low]

[ 34. Search for a Range ]

lets said an array [0,1,1,1,1,2,3]

if I want to find first 1's index which is 1,

• start, end = 0, len(nums)
• if nums[mid] < target
• after algorithm, start is the answer

if i want to find last 1's index which is 4,

• start, end = 0, len(nums)
• if nums[mid] <= target
• after algorithm, start - 1 is the answer

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        start, end = 0, len(nums)
        res = [-1, -1]
        # find left
        while start < end:
            mid = (start + end) / 2
            if nums[mid] < target:
                start = mid + 1
            else:
                end = mid
        if 0 <= start < len(nums) and nums[start] == target:
            res[0] = start
        
        start, end = 0, len(nums)
        # find right
        while start < end:
            mid = (start + end) / 2
            if nums[mid] <= target:
                start = mid + 1
            else:
                end = mid

        if 0 <= start - 1 < len(nums) and nums[start - 1] == target:
            res[1] = start - 1
        
        return res

To be continued...