Binary Search in python:

Writing this explanation down to understand my code thoroughly, if I need it for future reference, to become a better (future) software developer. I do get it, what I am doing through the code but if I can simply explain it to another person, then I'll understand it better, I wish I'd explain it to some friend, I have the internet as my solution to this.

My plan is first to explain the code I have written and then explain the code which is the most efficient one on leetcode.

First of all, let me tell you about Binary search.
It's a searching algorithm through which one divides a sorted array through the middle element in half, one is left section, one is right and if the target element we want to find in the array is present at the middle position, it returns that place, if the value is bigger or smaller than the sub-array is chosen accordingly and the loop continues till we find the target element or there is only one element left is the array.
It gives O(logN) time complexity because the array is divided into half every time.

1. Iterative (loops):

• Intuition: To use a loop for dividing the array and checking the position of the target element in the array, updating the first or last position checker of the sub-array.

• Approach: First, we create a class name Solution and in it, we create a function named search which requires nums (array) and the target value we are searching in the array. Low and high are the pointers which tell about the length of the array. Till the low is less than the high, the array still exists, the mid value is the half-integer division of (low+high) and we check if the middle value is the target value, if not then we see, if it's less, the target value is in the 2nd half of the array and we update the position of low to mid+1, and if it's more then we update the high's position to mid-1 and this keeps going on till we can find the element or the high and low have come on the opposite side now of original position, then we return -1 (the element doesn't exist).

  Complexity

• Time complexity: O(logn)

Code

class Solution: 
    def search(self, nums: List[int], target: int) -> int:

        low = 0 
        high = len(nums) - 1

        while low <= high: 
            mid = (low+high)//2 
        if nums[mid] == target: 
            return mid 
        elif nums[mid] < target: 
            low = mid+1 
        else: 
            high = mid-1

        return -1

2. Recursive:

• Intuition: For a function itself again and again for dividing the array and deciding the new positions of the first and last elements of the sub-array and make it return the value of the element position or -1 if the element is not present.

• Approach: We use recursion(a function calling itself) here. We call a function in which we take four parameters, array, the start and end position of the array (low, high) and the target value we are searching. Again, inside the function, we make the middle value equal to the half-integer division of low and high. The middle value is checked for being equal to the target value if not then we check if it's less or more than that if so we call the function again and update the value of low to mid - 1 if the target is more than the middle value, if not than high to mid - 1 and if the value of middle becomes equal to target value then mid is returned to its function call and this is how all the functions calls which were called get out of the stack since their work is done. If the value is not equal and the low has more value than the high, then -1 is returned to the called function and at the end, the answer is returned to its original call in the search function.

  Complexity

• Time complexity: O(logn)

  Code

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

  

  The major difference between the iterative and recursive versions of Binary Search is that the recursive version has a space complexity of O(log N) while the iterative version has a space complexity of O(1). Hence, even though the recursive version is easy to implement, the iterative version is efficient. (Credit: https://iq.opengenus.org/)

3. Fastest runtime solution

• Now, to the code which takes the least amount of runtime and is understandable to me as well. This is the same code as the iterative one, the only difference is that here we are directing using the argument values in the while loop and doing the calculations, in iterative, we made another function and checked first if the middle element is the target element and it was doing the calculations there and then returning the value. This has a 90ms of runtime on leetcode. Time complexity is O(logn).

  Code:

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

I hope this helped you, writing this made my concept clearer for sure.

Question link: https://leetcode.com/problems/binary-search/description/

If you have any suggestions on how I can improve my code or my explanation or if you have a better method, do share, I would love to know about that.

Till the next blog on my series of learning DSA-in-python!