[PYTHON] ABC146C (binary search)

Linear search

3, 7, 12, 15, 18, 23, 25, 26, 30
Suppose you want to find 25 from a sequence of numbers arranged in ascending order, such as. Linear search is a method of looking from the beginning in order as shown below.

a = [3, 7, 12, 15, 18, 23, 25, 26, 30]
HowManyLoops = 0
for i in a:
    if i == 25:
        break
    HowManyLoops += 1
print('a[{}]It is in.'.format(HowManyLoops))

a[6]It is in.

Binary search

Next, let's see how to do a binary search. Binary search is, as the name suggests, a method of reducing the number of elements to be searched while dividing into two. The method is as follows.

--Focus on the middle element, 18. -Compare 18 with 25, which is the element you want to find. ――25 is larger, so look for it from 23, 25, 26, 30 this time. ――Focus on 25, which is the middle element. -Compare 25 with 25, which is the element you want to find. --The search ends because it matches.

In this example, it ended up with only two searches. Let's actually look at the code.

a = [3, 7, 12, 15, 18, 23, 25, 26, 30]
pl = 0
pr = len(a)-1
HowManyLoops = 0
while True:
    HowManyLoops += 1
    pc = (pl + pr) // 2
    if a[pc] > 25:
        pr = pc - 1
    elif a[pc] < 25:
        pl = pc + 1
    else:
        print('a[{}]It is in.'.format(pc))
        break
    if pr < pl:
        print('The search failed.')
        break
        
print('The loop is{}There were times.'.format(HowManyLoops))

a[6]It is in.
There were two loops.

In this way, we were able to search in two loops. I will explain the source a little. The points are pl, which represents the leftmost index of the array we are looking at, pr, which represents the rightmost index, and pc, which represents the middle. If the element you want to search is on the right side of pc (pc <element you want to search), set pc + 1 as pl, and if the element you want to search is on the left side of pc (pc> element you want to search), set pc-1 as pr. Consider a new subarray. In this way, the number of elements in the subarray of interest is divided into two. Then, as a result of dividing into two, if the pc is found to be the element to be searched, the search is successful.

Search failure

So far we have seen the case of a successful search, but what if the search fails? In terms of source

if pr < pl:
    print('The search failed.')
    break

It is the part of. By the way, this part is a process that the search fails when the leftmost index of the partial array exceeds the rightmost index. Will this happen? To see this, the above array

a = [3,  7, 12, 15, 18, 23, 25, 26, 30]
#    0   1   2   3   4   5   6   7   8

Let's take a look at the steps to search for the number from 27. Of course, there is no 27 in this array, so the search will fail.

--Compare elements 18 and 27 of index 4 in the middle (pl = 0, pr = 8, pc = 4) --I found 27 on the right side, so let's search on the right side (pl = 4 + 1, pr = 8, pc = 6) [23, 25, 26, 30] --Compare elements 25 and 27 of index 6 in the middle (pl = 5, pr = 8, pc = 6) --I found 27 on the right side, so let's search on the right side (pl = 6 + 1, pr = 8, pc = 7) [26, 30] --Compare elements 26 and 27 of index 7 in the middle (pl = 7, pr = 8, pc = 7) --I found 27 on the right side, so let's search on the right side (pl = 7 + 1, pr = 8, pc = 8) [30] --Compare the index 8 element in the middle with 27 (pl = 8, pr = 8, pc = 8) --I found that 27 is on the ** left ** side, so let's search the left side ( pl = 8 </ font>, pr = 7 </ font> >, pc = 7)