A, logarithmic

　　

Second, the code

　　

 1 def binary_search(lists, item):
 2     #Low and high are used to track the portion of the list to look up in
 3     low = 0
 4     high = len(lists)-1
 5 
 6     while low <= high:  #As long as the range is not narrowed down to contain only one element
 7         mid = (low + high)/2 #Just check the middle element
 8 
 9         guess = lists[mid]
10         if guess == item: #Find the element
11             return mid
12         if guess > item: #The number is too high
13             high = mid-1
14         else:            #The difference is getting smaller
15             low = mid+1
16     #There is no specified element
17     return None
18 
19 my_list = [1, 3, 5, 7, 9]
20 print(len(my_list))
21 print (binary_search(my_list, 3))
22 print (binary_search(my_list, -1))

 

Three, running time

If the list contains 100 elements, you have to make up to seven guesses;

If the list contains 4 billion numbers, you have to make up to 32 guesses. Binary lookup runs in logarithmic time (or log time)

　　

　　

Big O notation

The big O notation is a special notation that indicates how fast the algorithm is.

The big O notation tells you how fast the algorithm is. For example, suppose the list contains n elements. A simple lookup requires checking each element, so n operations are required. Using big O notation, the running time is O(n).

What about seconds? No — the big O notation does not refer to speed in seconds.

The big O notation allows you to compare operands, and it tells you how fast the algorithm is running.

 

Here, in order from fastest to slowest, are five big O runtimes that you will often encounter.

O(log n), also known as logarithmic time, such algorithms include binary search. O(n), also known as linear time, involves simple lookups. O(n * log n), including quicksort, a faster sorting algorithm, described in Chapter 4. O(n2). Such algorithms include selective sorting, a slower sorting algorithm, described in Chapter 2. 5, O (n! Such an algorithm includes a very slow solution to the traveling salesman problem described next.

instructions

Binary lookup only works if the list is ordered.

2. When we talk about the speed of an algorithm, we are talking about how fast the running time increases as the input increases.

3. The running time of the algorithm is represented by big O notation.

O(log n) is faster than O(n). The former is faster than the latter when more elements need to be searched.

5. Algorithm running time is not measured in seconds.

 

Reference books: Algorithm diagrams