Binary Search 1

In [1]:

# Python code to implement iterative Binary Search
# Adapted from: https://www.geeksforgeeks.org/binary-search/

# Implement this code, and play with it until you understand it completely

# The function returns location of x in given sorted list arr  
# if present, else returns -1 
def binarySearch(arr, p1, p2, x): 
  
    while p1 <= p2: 

        print("checking the middle of this slice:",arr[p1:p2+1])
        mid = (p1 + p2)//2;     # floor division
          
        # Check if x is present at mid 
        if arr[mid] == x: 
            return mid
  
        # If x is greater, move p1 up to mid+1
        elif arr[mid] < x: 
            p1 = mid + 1
  
        # If x is smaller, move p2 down to mid-1
        else:
            p2 = mid - 1
      
    # If we reach here, then the element 
    # was not present 
    return -1
  
  
# Test list MUST BE SORTED IN ASCENDING ORDER
sortedList = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31 ] 
value = 27    # test with different values 

# Function call 
result = binarySearch(sortedList, 0, len(sortedList)-1, value) 
  
if result != -1: 
    print("Element is present at index", result) 
else: 
    print("Element is not present in sorted list")

checking the middle of this slice: [2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31]
checking the middle of this slice: [17, 19, 23, 27, 29, 31]
checking the middle of this slice: [27, 29, 31]
checking the middle of this slice: [27]
Element is present at index 9