Binary search algorithm in python

by

It would be much better to work with a lower and upper indexes as Lasse V. Karlsen was suggesting in a comment to the question.

This would be the code:

def binary_search(array, target):
    lower = 0
    upper = len(array)
    while lower < upper:   # use < instead of <=
        x = lower + (upper - lower) // 2
        val = array[x]
        if target == val:
            return x
        elif target > val:
            if lower == x:   # these two are the actual lines
                break        # you're looking for
            lower = x
        elif target < val:
            upper = x
  • lower < upper will stop once you have reached the smaller number (from the left side)
  • if lower == x: break will stop once you’ve reached the higher number (from the right side)

Example:

>>> binary_search([1,5,8,10], 5)   # return 1
1
>>> binary_search([1,5,8,10], 0)   # return None
>>> binary_search([1,5,8,10], 15)  # return None

More Related Contents:

  1. Implement pow(x,n)%d with integers only. (without making use of library functions) [duplicate]
  2. Cost of len() function
  3. What’s a good rate limiting algorithm?
  4. Pick N distinct items at random from sequence of unknown length, in only one iteration
  5. Find all combinations of a list of numbers with a given sum
  6. Why is Bubble Sort implementation looping forever?
  7. Edit Distance in Python
  8. Longest increasing subsequence
  9. Speed of calculating powers (in python)
  10. heapq with custom compare predicate
  11. How to trace the path in a Breadth-First Search?
  12. Finding index of nearest point in numpy arrays of x and y coordinates
  13. Rotate image and crop out black borders
  14. General bars and stars
  15. Python Integer Partitioning with given k partitions
  16. What is the complexity of the sorted() function?
  17. Non biased return a list of n random positive numbers (>=0) so that their sum == total_sum
  18. “For” loop first iteration
  19. Sliding window maximum in O(n) time
  20. How to hash a string into 8 digits?
  21. What algorithm does Python’s built-in sort() method use?
  22. NumPy grouping using itertools.groupby performance
  23. A set union find algorithm
  24. Finding the most frequent character in a string
  25. How can I fit a Bézier curve to a set of data?
  26. All possible paths from one node to another in a directed tree (igraph)
  27. fastest method of getting k smallest numbers in unsorted list of size N in python?
  28. Mergesort with Python
  29. Find non-common elements in lists
  30. Algorithm for solving Sudoku

Leave a Comment