Leetcode #704 Binary Search

Binary Search is a one of the efficient search algorithm that uses a lot for various reasons.

 

It is super simple to demonstrate and how it works.

 

First lets say, we have size of 8 sorted array [0, 1, 3, 7, 9, 14, 16, 19] and the target number is 16 and we are trying to find the index of the target.

 

1. We set most left and most right and then we set the mid point which is 9 in this case.

 

2. If the mid point is smaller than target we can eliminate everything from the most left to midpoint and move most left index to index of mid point + 1 or if the mid point is larger than the target we can eliminate everything from the most right to mid point and move most right index to mid point index - 1

 

3. If neither of the case that means we found the target.  

 

4. Loop 2 - 3 until left most is smaller or equal to right most.

 

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) -1

        while left <= right:
            # for python we can do this 
            # m = (left + right) // 2
            
            # However, for other languages overflow cna happen
            # to Prevent Overflow 
            m = left + ((right - left) // 2)
            if nums[m] < target:
                left = m + 1
            elif nums[m] > target:
                right = m - 1
            else:
                return m

        # target does not exist in nums so return -1
        return -1