**Challenge**: How to find a given value in a sorted list?

**Example**: Say, you have a sorted list:

[1, 4, 10, 42, 99, 102, 103, 999]

Your goal is to find the index of the element 103 in the list. Do you have to check all elements to do this?

Well, only if you used the …

## Naive List Search Algorithm

A ** naive algorithm** would

**in the list against the searched value.**

*compare each element*For example, consider a list of **1024** elements. The naive algorithm performs in the order of **1024** **comparisons in the worst-case**. ?

*(In case you wonder, this is real bad—checking any element in a sorted list to find a specific element is a dumb-ass thing to do!)*

List Size | Number of Comparison Needed (Worst-Case) |
---|---|

2 | 2 |

1,024 | 1,024 |

42,000,000 | 42,000,000 |

… | … |

n | n |

In computer science, the worst-case runtime complexity can be expressed via the Big-O notation. We say, for `n`

elements in a list, the naive algorithm needs `O(n)`

comparisons. The O-function defines the asymptotic worst-case growth.

Fortunately, there’s a better and faster way to find an element in a sorted list!

## Binary Search Algorithm in Python

The function `bsearch`

is a more effective way to find a value in a sorted list. For `n`

elements in the list, it needs to perform only `O(log(n))`

comparisons.

Here’s the code:

def bsearch(l, value): # search only in index interval (lo:hi) lo, hi = 0, len(l)-1 while lo <= hi: mid = (lo + hi) // 2 if l[mid] < value: # Mid element is smaller # --> skip all left elements lo = mid + 1 elif l[mid] > value: # Mid element is larger # --> skip all right elements hi = mid - 1 else: # We've found the value! return mid return -1

**Exercise**: Take a guess—what’s the output of this code snippet when passing the following three function calls?

l = [0, 1, 2, 3, 4, 5, 6] x = 6 print(bsearch(l,x)) x = 0 print(bsearch(l,x)) x = 3 print(bsearch(l,x))

In case you guessed the following three values, you’ve guessed right!

6 0 3

Applied to a list of 1024 elements, `bsearch`

requires only up to `log(1024)=10`

comparisons. Hence, `bsearch`

is much faster than the naive comparison algorithm!

In computer science, the worst-case runtime complexity can be expressed via the Big-O notation. We say, for `n`

elements in a list, the naive algorithm needs `O(n)`

comparisons. The O-function defines the asymptotic worst-case growth.

List Size | Number of Comparison Needed (Worst-Case) |
---|---|

2 | log(2) = 1 |

1,024 | log(1,024) = 10 |

42,000,000 | log(42,000,000) = 25 |

… | … |

n | log(n) |

Yes, that’s about 25 comparisons for a list with 42,000,000 elements!!

? <— You

## Why is Bsearch so fast?

The naive algorithm compares all elements with the searched value.

Instead, `bsearch`

uses the property that the list is sorted in an ascending manner.

- It checks only the element in the middle position between two indices
`lo`

and`hi`

. - If this middle element is smaller than the searched value, all left-hand elements will be smaller as well because of the sorted list. Hence, we set the lower index
`lo`

to the position right of the middle element. - If this middle element is larger than the searched value, all right-hand elements will be larger as well. Hence, we set the upper index
`hi`

to the position left of the middle element. - Only if the middle element is exactly the same as the searched value, we return the index of this position.

This procedure is repeated until we find the searched value or there are no values left. In each loop iteration, we ** reduce the search space**, i.e., the number of elements between

`lo`

and `hi`

, by half.## Interactive Shell Binary Search Python

You can try the `bsearch`

function in the following interactive shell in your browser:

**Exercise**: Guess the output and run the shell to compare it against the real output!

## Code Puzzle Binary Search Algorithm

Another great way to improve your understanding of programming concepts such as the binary search algorithm is to solve code puzzles:

**Exercise**: Are you a master coder? Test your skills now! Click the puzzle image and try to solve it in our interactive puzzle app!