Created
March 10, 2018 08:21
-
-
Save meetzaveri/7a343a1a708caea616486816b3a3d54c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Python Program for recursive binary search. | |
# Returns index of x in arr if present, else -1 | |
def binarySearch (arr, l, r, x): | |
# Check base case | |
if r >= l: | |
mid = l + (r - l)/2 | |
# If element is present at the middle itself | |
if arr[mid] == x: | |
return mid | |
# If element is smaller than mid, then it | |
# can only be present in left subarray | |
elif arr[mid] > x: | |
return binarySearch(arr, l, mid-1, x) | |
# Else the element can only be present | |
# in right subarray | |
else: | |
return binarySearch(arr, mid+1, r, x) | |
else: | |
# Element is not present in the array | |
return -1 | |
# Test array | |
arr = [ 2, 3, 4, 10, 40 ] | |
x = 10 | |
# Function call | |
result = binarySearch(arr, 0, len(arr)-1, x) | |
if result != -1: | |
print "Element is present at index %d" % result | |
else: | |
print "Element is not present in array" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I have a question with this code. How do you make sure that mid is an interger every single time? say like your search space is array = [1,2,3,4], then l=0, r=3, mid = 1.5?