2.6.1 Binary Search Iterative Method

Name: 2.6.1 Binary Search Iterative Method
Uploaded: 2018-01-29T20:22:51.000Z
Duration: 38 min 36 s

Binary Search

In this section, the speaker explains binary search as a searching technique that follows the divide and conquer strategy. The speaker also explains how to perform binary search and compares it with linear search.

How Binary Search Works

Binary search is performed on a sorted list of elements.

To perform binary search, we need two index pointers: low and high. We calculate mid as (low + high) / 2.

If the key element we are searching for is greater than mid, we ignore the left half of the list and focus on the right half. If it's smaller, we ignore the right half and focus on the left half.

We repeat this process until we find the key element or determine that it's not present in the list. Each repetition reduces our search space by half.

Comparing Binary Search with Linear Search

For binary search to work, the list must be sorted first, which can take extra time compared to linear search where sorting is not required. However, once sorted, binary search can find an element much faster than linear search because it reduces our search space by half at each step.

In contrast, linear search requires us to compare each element in sequence until we find what we're looking for or reach the end of the list. This means that in worst-case scenarios where an element is at the end of a long list, linear search can take much longer than binary search to find it.

Examples

Example 1: Searching for Key Element 12

To perform binary search for key element 12 on a list of size 15, we start with low = 1 and high = 15. We calculate mid as (low + high) / 2 = 8.

Since the key element is smaller than mid, we ignore the right half of the list and focus on the left half. We set high to mid - 1 = 7 and recalculate mid as (low + high) / 2 = 4.

Since the key element is greater than mid, we ignore the left half of the list and focus on the right half. We set low to mid + 1 = 5 and recalculate mid as (low + high) / 2 = 6.

Since the key element is smaller than mid, we ignore the right half of the list and focus on the left half. We set high to mid - 1 = 5 and recalculate mid as (low + high) / 2 = 5.

Since low == high == mid, we have found our key element at index 4 in just two comparisons.

Example 2: Searching for Key Element Not Present in List

To perform binary search for key element 30 on a list of size 15, we start with low =1 and high =15. We calculate mid as (low+high)/2=8.

Since our key element is greater than mid, we ignore the left half of the list and focus on the right half by setting low to mid+1=9.

We then calculate new value for middle which is equal to (low+high)/2=(9+15)/2=12.

Our key element is still greater than middle so again we will ignore left part of this sub-list.

Now our new value for middle becomes equal to (low+high)/2=(13+15)/2=14.

Since our key element is still greater than middle, we will ignore left part of this sub-list again.

Now low becomes equal to 15 and high becomes equal to 15. We calculate new value for middle which is equal to (low+high)/2=15/2=7.5 but since we can't have a decimal index, we take the floor value which is 7.

Since our key element is smaller than middle, we will ignore right part of this sub-list now.

Now low becomes equal to 15 and high becomes equal to 6. Since low>high, it means that the key element is not present in the list.

Conclusion

Binary search is a searching technique that follows the divide and conquer strategy. It works by repeatedly dividing a sorted list into two halves until it finds the key element or determines that it's not present in the list. Compared with linear search, binary search can find an element much faster because it reduces our search space by half at each step. However, sorting the list first can take extra time compared with linear search where sorting is not required.

Binary Search Algorithm

In this section, the speaker explains how to implement a binary search algorithm. They provide an example of how to trace the algorithm and explain how it works when searching for an element.

Implementing Binary Search Algorithm

If the number is greater than 29, look on the right-hand side.

Change low to 9 so that low becomes mid plus 1 (9), and this remains 15. So, 9 plus 15 by 2 is 12. Now, the new meta value is L = min again.

The mid of this listens to a log basis. Check if it's the number 30; no, it's not. It's 47, so our number is smaller.

If the number we are searching for is less than a[mid], then change high to mid minus one (hi will become eleven), and this remains nine. Notice that twenty by two is ten, so new lid will be at ten.

Is it the number that you are searching? No, it's not; thirty is smaller. So go on the left-hand side.

Change low too should change to mid plus one (low becomes ten).

This process will repeat until the element is found.

Writing Binary Search Algorithm as a Function

Write an algorithm for binary search with three parameters - array of elements, size (number of elements), and key to be searched - and returns index of element found.

Instead of writing an algorithm, write it like a function where low will be at one and high will be at n (integer variables Ln and H).

Find out mid using low + high / -.

At mid check if key equals A[mid]. If so, then the element is found. Return the mid.

If key element is less than A[mid], change high to mid minus one (H should be changed to mid a minus 1).

If it's neither equal nor less, change low too should change to mid plus 1.

Run this loop as long as low is less than or equal to high. If low became greater than high, return not found.

Tracing Binary Search Algorithm with a Tree

Trace the algorithm using a tree for the example given earlier.

First time when calling this algorithm, calculate mid from 1 to 7 (4) if searching on left-hand side and 12 if searching on right-hand side.

If the element is less than 12, calculate mid for left-hand side (2) and right-hand side (6).

On the left-hand side of this one is seven; on the right-hand side of this one is seven and left of twelve is nine.

Repeat until element is found.

Overall, in this section, we learned how to implement binary search algorithms and write them as functions. We also saw how tracing an algorithm with a tree can help us understand how it works when searching for an element.

Binary Search Algorithm

In this section, the speaker explains how binary search works and analyzes its time complexity.

How Binary Search Works

The algorithm starts by dividing a sorted list into two halves.

It then compares the middle element of the list with the target element.

If they match, it returns the index of that element. If not, it repeats the process on either the left or right half of the list until it finds a match or determines that the target element is not in the list.

Time Complexity Analysis

The time taken by binary searches is logarithmic.

The maximum number of comparisons required depends on the height of a tree, which is log n.

The minimum time for searching for an element present in the middle is order 1.

The worst-case scenario occurs when searching for an element that is not present in the list. In this case, it takes log n comparisons to determine that it's not there.

Conclusion

In this section, the speaker concludes by summarizing how binary search works and its time complexity analysis.

Summary

Binary search algorithm divides a sorted list into two halves and compares each half with a target value until it finds a match or determines that there's no such value in the list.

Its time complexity analysis shows that binary search has logarithmic time complexity.

Best case scenario occurs when searching for an element present in mid with order 1

Worst case scenario occurs when searching for an element not present in mid with order log n

Average case scenario can be calculated by adding up all comparisons and dividing them by number of elements