python实现：查找列表中的元素（线性查找和二分查找）

python实现二分查找的两种方式

二分查找：时间复杂度：O(logn)
使用这种方法的必须是 按关键字大小 有序排列的 顺序存储结构。
这里使用升序排列的数组

class BinarySearch:
    # 非递归
    def binarysearch1(self, arr, x, l, r):
        # 循环直到找到或是确认没有为止
        while True:
            # 右边界大于等于左边界时执行
            if r >= l:
                # 索引中间值，需要保证为int
                mid = int(l + (r - l) / 2)
                # 若刚好等于中间值
                if x == arr[mid]:
                    return mid
                # 落在右边
                elif x > arr[mid]:
                    l = mid + 1
                # 落在左边
                else:
                    r = mid - 1
            else:
                return False

    # 递归
    def binarysearch2(self, arr, x, l, r):
        # 右边界大于等于左边界时执行
        if r >= l:
            # 索引中间值，需要保证为int
            mid = int(l + (r - l) / 2)
            # 若刚好等于中间值
            if x == arr[mid]:
                return mid
            # 落在右边，替换最小值，递归
            elif x > arr[mid]:
                return self.binarysearch2(arr, mid + 1, r, x)
            # 落在左边，替换最大值，递归
            else:
                return self.binarysearch2(arr, l, mid - 1, x)
        else:
            return False

    def test(self):
        arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        x = 5
        l = 0
        r = len(arr) - 1
        n1 = self.binarysearch1(arr, x, l, r)
        # n2 = self.binarysearch2(arr, x, l, r)
        if n1:
            print("元素的索引为 {}".format(n1))
        else:
            print("找不到元素！")

BinarySearch().test()
——>> 元素在数组中的索引为 4

python实现线性查找（遍历）

时间复杂度：O(n)

class LinearSearch:
	# 遍历对比，简单粗暴
    def linearsearch(self, arr, x, l):

        for i in range(l):
            if (arr[i] == x):
                return i
        return False
	# 测试
    def test(self):
        arr = [1, 5, 6, 4, 2, 5, 7, 9, 4]
        x = 5
        l = len(arr)
        n = self.linearsearch(arr, x, l)
        if n:
            print("元素的索引为:", n)
        else:
            print("找不到元素！")
            
 LinearSearch().test()
 ——>>元素的索引为: 1