binary_search.md

二分法查找

二分法查找，顾名思义，二分、二分就是分成两半呗。(有的翻译是折半法搜索比如SICP里翻译的就是折半法搜索)。它的复杂度为O(logn)，在列表(已排序)中对给定值value进行查找并输出其索引(index)值。

# -*- coding: utf-8 -*-


def binary_search(lst, value):
    left, right = 0, len(lst) - 1

    while left <= right:
        middle = (left + right) // 2 # 取`lst`中值索引

        if value > lst[middle]:
            left = middle + 1 # value大于`lst`中值，让左边界等于 middle + 1
        elif value < lst[middle]:
            right = middle - 1 # 类似上
        else:
            return "The value's index is {}".format(middle)
    return "There is no {}".format(value)

if __name__ == '__main__':
    lst = [1, 3, 5, 7, 9]
    value = int(input("Please input the value(1-10): "))
    print(binary_search(lst, value))

再来个递归(recursion)版的吧， 不作过多解释啦！

# -*- coding: utf-8 -*-


def binary_search_rec(lst, value, left, right):
    middle = (left + right) // 2

    if left > right:
        return "I'm sorry, there is no {}".format(value)

    if value < lst[middle]:
        return binary_search_rec(lst, value, left, middle - 1)

    elif value > lst[middle]:
        return binary_search_rec(lst, value, middle + 1, right)

    else:
        return "Congratulations, the value's({}) index is {}".format(value, middle)


if __name__ == '__main__':
    lst = [1, 3, 5, 7, 9]
    left, right = 0, len(lst)
    value = int(input("Please input the value: "))
    print(binary_search_rec(lst, value, left, right))

昨天面试,面试官出了一道算法题:

有一个数组,其内元素先递增后递减,请找出其中的最大值.

对于我来说,当时第一个想起来的是,排序但是转念间就知道肯定不是最好的啦.于是就在哪儿想啊想,还是想不起来.气氛挺尴尬的,外面也挺冷的(电话面试,外面安静).我想不起来,面试小哥也不急着催我,最后也算是在小哥的提示下,想起了怎么做啦!(太感谢小哥啦, 小哥好人! 喂, 你们几个不许笑啊喂!)

当然是二分啦,下面是算法实现!

# coding=utf-8


def search_max_num(seq, left, right):
    mid = (right + left) // 2
    if left > right:
        return seq[mid]
    if seq[mid] > seq[mid - 1]:
        return search_max_num(seq, mid + 1, right)
    else:
        return search_max_num(seq, left, mid - 1)

if __name__ == "__main__":
    seq = [32, 55, 54, 54, 54, 54, 32, 15, 6, 4, 2, 1]
    print(search_max_num(seq, 0, len(seq)))