Binary Search

What is binary search?

This is an algorithm that searches for a target number in an ordered numeric data structure by dividing the search area in half each time. This results in a time complexity of O(log n)

What does O(log n) give a hint to and mean?

It hints that binary search should be used and log n means basically if you have an input size of n, the maximum number of checks needed is log n. So basically if n = 2 then it would be O(1). If n = 4 it would be O(2), because we would have to check 2 sets of 2.

How to do the binary search problem?

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start_index = 0
        end_index = len(nums) - 1


        while start_index <= end_index:
            middle_index = (start_index + end_index) // 2

            if target == nums[middle_index]:
                return middle_index
            elif target < nums[middle_index]:
                end_index = middle_index - 1
            elif target > nums[middle_index]:
                start_index = middle_index + 1
        return -1    	

What does // do/mean?

It is the floor division operator and means to divide and round down.