Searching and Recursion
We'll be covering Binary Search and Recursion in this lesson. The problems on DomeCode might have implementation questions involving the use of other search techniques but knowing Binary Search is the first step. And if you understand the implementation of the algorithms well enough, you can deduce the algorithms to basic logic and build up from there. We'll add other searching techniques in the future as well but Binary Search is the basic efficient search technique you should be knowing of. Try out the implementation in the editor below and tinker with the code to understand how everything ties in together. Also, Big O of N is explained in Binary Search: Efficiency video.
Binary Search and it's Efficiency
Implementation of Binary Search using the Iterative Approach
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
return binarySearchAppr(arr, mid+1, end, x)
# Element is not found in the array
arr = sorted(['t','u','t','o','r','i','a','l'])
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index "+str(result))
print ("Element is not present in array")
Pro Tip: If you're unsure about the code but know the logic behind it, have some pseudo-code ready for your own understanding first.
Try the Binary Search Implementation using the Recursive approach as an exercise for your brain.