糗百面试题目

script.py

# coding=utf8

"""
    思路
    ~~~~

    1. 按行读取文件, 三列入列表start_lst, end_lst, code_lst
    2. 对start_lst进行二分法查找，直到找到离目标ip地址x最近的元素start和其
       在start_lst中的索引i， 使得恰好有
         start=start_lst[i]<=x
       如果找不到则直接报告查找失败
    3. 取出end = end_lst[i]， 若有 x<=end，则查找成功，返回code_lst[i]
       否则失败！


    用法
    ~~~~

    查询指定ip的区号::

        <script> ip-lib.txt target_ip

    输出`-1` 代表查找失败。

    测试
    ~~~~

    跑测试的方法::

        <script> ip-lib.txt test

"""


import random
import sys
import time


def bin_search(lst, target):
    '''bin search target in lst, find the element closest to target
    , then return its index'''
    low, high = 0, len(lst)-1

    while low <= high:
        mid = (low+high)/2
        mid_var = lst[mid]

        if mid_var < target:
            low = mid + 1
        elif mid_var > target:
            high = mid - 1
        else:
            low = mid + 1
            break

    return low - 1  # return -1 for failure


def find_code(index, start_lst, end_lst, code_lst, target_ip):
    """find code by index, return -1 for failure"""
    if index >= 0 and start_lst[index] <= target_ip <= end_lst[index]:
        return code_lst[index]
    return -1


def main():

    test = False   # flag: if in a test

    # parse args
    ip_lib, arg = sys.argv[1: 3]

    try:
        ip = int(arg)
    except ValueError:  # Not integer
        if arg == 'test':
            test = True
        else:
            sys.exit(1)  # wrong input

    # read ip-lib.txt
    with open(ip_lib) as f:
        lines = f.readlines()
    # remove \n at the end of each line
    lines = [line.rstrip('\n') for line in lines]

    # 3 columns => into 3 list
    start_lst, end_lst, code_lst = [], [], []

    for line in lines:
        start, end, code = map(int, line.split(' '))  # cast str to int
        # append each to their list
        start_lst.append(start)
        end_lst.append(end)
        code_lst.append(code)

    if not test:  # not a test, search target ip, and return code
        # search start_lst
        i = bin_search(start_lst, ip)
        print find_code(i, start_lst, end_lst, code_lst, ip)
    else:  # run a test with 1000 target_ip
        ips = [random.randint(start_lst[0], end_lst[-1]) for x in range(1000)]

        start_time = time.time()

        for ip in ips:
            i = bin_search(start_lst, ip)
            print ip, find_code(i, start_lst, end_lst, code_lst, ip)

        end_time = time.time()
        print "1000 IP search in %.3fs" % (end_time - start_time)


if __name__ == '__main__':
    main()

使用方法:

python script.py ip-lib.txt 3688366079   

返回 -1 代表失败

python script.py ip-lib.txt 3688366080

测试明天我起早写，另外这个脚本写的好难看， 一起改改