search algorithm

Posted on | In
Words count in article: 79 | Reading time ≈ 1

Linear Search and Binary Search

Time complexity：\(O(n)\) 

1
2
3
4
5
def linear_search(ls,val):
    for index,value in enumerate(ls):
        if value == val:
            return index
    return -1

Time complexity：\(O(log n)\) 

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search(ls,val):
    left = 0  #左指针
    right = len(ls)-1  #右指针
    while left <= right:
        mid = (left+right)//2
        if ls[mid] == val:
            return mid
        elif ls[mid]<val:
            left = mid+1
        else:
            right = mid-1
    return -1

I do not accept rewards, but you can donate to the public welfare of China.
0%