In my previous article I gave a brief introduction on data structures and the different types. In this article, we will dive expound on ways of analyzing the efficiency of algorithms.

## Binary Search

Binary search is an algorithm whose input is a sorted list of elements. Suppose you are searching for a word in a dictionary starting with M. You could start at the beginning and keep flipping until you get to M; but this would be a bad approach. It makes more sense starting from near the middle.

In binary search, if the element you are looking for is in the list, it returns its position, otherwise None. Binary search only works when your list is sorted.

Let's implement binary search in python

The *binary_search* function takes a **sorted** array *nums* and an item.

```
def binary_search(nums, item):
```

If the item is in the array, the function returns it position. To keep track of what part of array you have to search through, use *low* for the lower part of the array and *high* for the upper part of the array.

```
low = 0
high = len(nums) - 1
```

While you haven't narrowed it down to one element check the *mid* element.

```
while low <= high:
mid = (low + high) // 2
guess = nums[mid]
```

If the *guess* is equal to the *item*, the index is returned. If the guess is too low, you update *low* accordingly and if too high, update *high*.

```
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return None
```

Full Code:

```
def binary_search(nums, item):
low = 0
high = len(nums) - 1
while low <= high:
mid = (low + high) // 2
guess = nums[mid]
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return None
nums = [20, 38, 74, 90, 98, 110]
print(binary_search(nums, 98))
print(binary_search(nums, 22))
```

Now let's run the code

```
$ python3 binary_search.py
4
None
```

The first statement returns 4, since 98 is at index 4 on the list and the second statement returns None since 22 is not on the list.

**Running time**

The running time of an algorithm grows with the input size, although it may vary for different inputs of the same size. Binary search runs in *logarithmic time*. If a list has 128 names, the maximum number of steps it would take is 7(2 pow 7 is 128).

## Big O Notation

Big O notation is a special notation that is used to show how an algorithm scales with respect to the size of its growth.Growth can be sublinear, linear, superlinear etc. You need to know how the running time increases as the size of the list increases. It establishes a *worst case scenario*. Big O notation lets you compare the number of operations. For example, binary search needs log n operations to

to check a list of size n. The running time in Big O notation is **O(log n)**.

Common Big O run times sorted from fastest to slowest:

O(log n) -known as

*log time*. Example : Binary searchO(n) - known as

*linear time*. Example : Simple searchO(n * log n) : A fast sorting algorithm like quicksort

O(n2) : A slow sorting algorithm like selection sort.

O(n!) : A really slow algorithm like the travelling salesperson.

**Conclusion**

The speed of an algorithm is not measured in seconds but in growth of the number of operations. Instead, we talk about how quickly the tun time of an algorithm increases as the size of the input increases. In my next article, we will cover on the different Big O run times.

## Discussion (0)