Skip to content

Instantly share code, notes, and snippets.

@anil477
Last active January 28, 2017 06:33
Show Gist options
  • Save anil477/d95b4146aa5d52bb8a77d029dcbbd58a to your computer and use it in GitHub Desktop.
Save anil477/d95b4146aa5d52bb8a77d029dcbbd58a to your computer and use it in GitHub Desktop.
Ceil of a number using binary search
# http://www.geeksforgeeks.org/search-floor-and-ceil-in-a-sorted-array/
def binarySearch(arr, l, r, x):
if x < arr[l]:
return arr[l]
if x > arr[r]:
return arr[r]
while l <= r:
mid = l + (r - l) / 2
# Check if x is present at mid
if arr[mid] == x:
return arr[mid]
# the two if cond at the top prevents out of bound exception
if arr[mid] < x and arr[mid + 1] > x:
return arr[mid + 1]
# If x is greater, ignore left half
if arr[mid] < x:
l = mid + 1
# If x is smaller, ignore right half
else:
r = mid - 1
# If we reach here, then the element was not present
return -1
# Test array
arr = [2, 3, 5, 10, 40]
x = 1
# Function call
result = binarySearch(arr, 0, len(arr) - 1, x)
if result != -1:
print "Ceil Is %d" % result
else:
print "None"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment