python 之 查找

注：

算法演示工具： https://algorithm-visualizer.org/

参考：https://www.runoob.com/python3/python3-examples.html

参考：《算法图解》

环境： Visual Code Python2.7

线性查找

简介：按照一定的顺序检查数组中的每一个元素，直到寻找到指定的值结束。

时间： O(n)

图示：

示例：

# -*- coding:UTF-8 -*-
#!/usr/bin/env python

import sys

# 查找指定值
def line_search(arr, value):
    for i in range(1,len(arr)):
        print(u'-->查找数组中数值:{0}'.format(arr[i]))
        if arr[i] == value:
            return i

    return -1

if __name__ == '__main__':
    arr = [-5,10,8,6,0,5]
    searchValue = 5
    print(u'查找数组:{0}, 查找数值:{1}'.format(arr, searchValue))
    index = line_search(arr,searchValue)
    if index != -1:
        print(u'元素在数组中的索引为{0}'.format(index))
    else:
        print(u'未找到!!!')

'''
查找数组:[-5, 10, 8, 6, 0, 5], 查找数值:5
-->查找数组中数值:10
-->查找数组中数值:8
-->查找数组中数值:6
-->查找数组中数值:0
-->查找数组中数值:5
元素在数组中的索引为5
'''

二分查找

简介：又称折半查找，适用于在有序数组中查找特定元素。搜索过程从数组的中间开始查找，如果特定元素小于或大于中间元素，则在数组大于或小于中间元素的那一半查找。

时间：O(logN)

图示：

示例：

# -*- coding:UTF-8 -*-
#!/usr/bin/env python

# UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-1: ordinal not in range
import sys
reload(sys)
sys.setdefaultencoding('utf8')

def binary_search(_list, searchNum):
    low = 0                             # 最小数下标
    high = len(_list) - 1               # 最大数下标

    # low <= high时才能证明中间有数
    index = 1
    while low <= high:
        mid = (low+high)/2              # 中间数下标 
        print(u'查找的次数为:{0}, low = {1}, high = {2} mid = {3}'.format(index, low, high, mid))
        guess = _list[mid]
        if guess == searchNum:
            return mid
        elif guess > searchNum:         # 中间数大于指定数字，最大数下标移动  
            high = mid - 1
        else:
            low = mid + 1

        index += 1

    return None

if __name__ == '__main__':
    maxCount = input(u'请输入列表的最大数值:'.encode('gbk'))
    searchNum = input(u'请输入要查找的数值:'.encode('gbk'))

    print(u'搜寻顺序列表,数据为0 ~ {0}, 查找:{1}'.format(maxCount, searchNum))
    index = binary_search(range(maxCount), searchNum)
    print(u'查找出的索引为:'+ str(index))


'''
请输入列表的最大数值:1000
请输入要查找的数值:569
搜寻顺序列表,数据为0 ~ 1000, 查找:569
查找的次数为:1, low = 0, high = 999 mid = 499
查找的次数为:2, low = 500, high = 999 mid = 749
查找的次数为:3, low = 500, high = 748 mid = 624
查找的次数为:4, low = 500, high = 623 mid = 561
查找的次数为:5, low = 562, high = 623 mid = 592
查找的次数为:6, low = 562, high = 591 mid = 576
查找的次数为:7, low = 562, high = 575 mid = 568
查找的次数为:8, low = 569, high = 575 mid = 572
查找的次数为:9, low = 569, high = 571 mid = 570
查找的次数为:10, low = 569, high = 569 mid = 569
查找出的索引为:569
'''