The Binary Search
In computer science, binary search, also known as halfinterval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.
It is possible to take greater advantage of the ordered list if we are clever with our comparisons. In the sequential search, when we compare against the first item, there are at most n−1
more items to look through if the first item is not what we are looking for. Instead of searching the list in sequence, a binary search will start by examining the middle item. If that item is the one we are searching for, we are done. If it is not the correct item, we can use the ordered nature of the list to eliminate half of the remaining items. If the item we are searching for is greater than the middle item, we know that the entire lower half of the list as well as the middle item can be eliminated from further consideration. The item, if it is in the list, must be in the upper half.
We can then repeat the process with the upper half. Start at the middle item and compare it against what we are looking for. Again, we either find it or split the list in half, therefore eliminating another large part of our possible search space. Figure 3 shows how this algorithm can quickly find the value 54. The complete function is shown in CodeLens 3.
0 comments Comments
Leave a comment
 Basic Data Structures

Objectives

What Are Linear Structures?

What is a Stack?

The Stack Abstract Data Type

Implementing a Stack in Python

What Is a Queue?

The Queue Abstract Data Type

Implementing a Queue in Python

What Is a Deque?

The Deque Abstract Data Type

Implementing a Deque in Python

Lists

The Unordered List Abstract Data Type

Implementing an Unordered List: Linked Lists

The Ordered List Abstract Data Type

Implementing an Ordered List

Vocabulary and Definitions

 Sorting and Searching
 Trees and Tree Algorithms
 Graphs and Graph Algorithms