Two points search

• 1. In order to find
• 2. Two points search

1. In order to find

Sequential search starts from the first item in the list , Search in turn , Go to the end of the list or find the element .

 example ： Find a number in order from the list , There is a return subscript , Otherwise return to None

# Find a number in a list ,
# If there is a subscript that returns the number , Otherwise return to None
def f(data_list, value):
for i in data_list:
if value == i:
return data_list.index(i)
break
else:
return None
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(f(data, 6)) # Output 5
print(f(data, 15)) # Output None

2. Two points search

Be careful ： The list must be ordered

Ideas ：

1. Give a range first such as ：1-100
2. Find half of this range first mid, That's numbers 50（ Subscript to be 49）
3. If you look big , Set the maximum range to mid-1, At this time, the range is number 1-49（ Subscript range ：0-48）
4. If it's too small , Set the minimum range to mid+1, At this time, the range is number 50-100（ Subscript range ：51-100）
5. repeat 2-4 step , Until we find this number

for example ： stay 1 To 100 Between looking for 1, Will find the middle subscript first 49, If you look big Just go mid To the right , If the search is small Just go mid Look for... On the left

data_list = [i for i in range(1, 101)] # List with lookup 
value = 2 # Number to find 
left = 0 # Leftmost subscript 
right = len(data_list) - 1 # Right most subscript 
x = 1
while left <= right: # The left subscript is smaller than the right subscript , Look in the list for 
mid = (left + right) // 2 # to be divisible by , Take the middle subscript position 
print('\n The first {} Time , Take the middle subscript as :{}'.format(x, mid))
if data_list[mid] == value: # If the number you want to find is equal to the number in the middle , Then print the index 
print(' The subscript of this number is ：', mid)
break
elif data_list[mid] > value:
right = mid - 1
else:
left = mid + 1
print('\t\tleft：{}, right:{}'.format(left, right))
x += 1
else:
print(None)

def search(data_list, value):
""" :param data_list: List to find :param value: The number to find :return: Subscript or None """
left = 0 # The leftmost subscript of the list 
right = len(data_list) - 1 # Subscript to the right of the list 
while left <= right: # The left subscript is smaller than the right subscript , Look in the list for 
mid = (left + right) // 2 # to be divisible by , Take the middle subscript position 
if data_list[mid] == value: # If the number you want to find is equal to the number in the middle , The index is returned 
return mid
elif data_list[mid] > value:# If mid Greater than the number to find , take right Reassign to the left of the middle subscript ( That is to say mid-1)
right = mid - 1
else:
left = mid + 1
# print('mid:{}, left：{},right:{}'.format(mid, left, right))
else:
return None
a = [i for i in range(100)]
print(search(a, 2))