Posted By

nickleeh on 10/30/08


Tagged

python


Versions (?)

Binary Search


 / Published in: Python
 

  1. def recBinSearch(x, nums, low, high):
  2. if low > high: # No place left to look, return -1
  3. return -1
  4. mid = (low + high) / 2
  5. item = nums[mid]
  6. if item == x: # Found it! Return the index
  7. return mid
  8. elif x < item: # Look in lower half
  9. return recBinSearch(x, nums, low, mid-1)
  10. else: # Look in upper half
  11. return recBinSearch(x, nums, mid+1, high)
  12.  
  13. #We can then implement our original search function using a suitable call to the recursive binary search, telling
  14. it to start the search between 0 and len(nums)-1
  15. def search(x, nums):
  16. return recBinSearch(x, nums, 0, len(nums)-1)

Report this snippet  

You need to login to post a comment.