[Neetcode/Array, Binary Search] Binary Search

1. Linear Search

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if target == nums[i]:
                return i
        return -1

• Time Complexity: O(n)

2. Binary Search

Binary Search, Tree -> Narrow down the scope w/ starter, end and middle!

There are two ways for a Binary Search.

1. Two pointer + while loop
2. Recursion

2.1. Two pointer + while loop

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

• Time Complexity: O(logn)

2.2. Recursion

- call function in the funcion
- add helper() function

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums)-1
    
        def helper(start, end):
        # base case
            if start == end:
                if target == nums[end]:
                    return end
                else:
                    return -1 # if target does not exist in the list, return -1
            
            middle = (start + end) // 2

            if target <= nums[middle]:
                return helper(start, middle)
            else:
                return helper(middle+1, end)      

        return helper(start, end)

• Time Complexity: O(logn)