珠玉のプログラミングのお題を python で書いてみた : 2

#!/bin/env python

"""
2.2 the binary search in everywhere(P13-15)
Problem A finding the lack of integer
"""
import random

# global
ERROR = -1
max_num = 10
element_num = 9
max_digit = 8

def main():
    # input data
    input_data = random.sample(xrange(0,max_num), element_num)
    print "input  : " + str(input_data)
    
    # investigate lack number
    lack_num = lacking_binary_search(input_data, max_digit, '')
    print "lack number : ", lack_num
    
    # verify lack number
    for i in input_data:
        if i == lack_num:
            return ERROR

def lacking_binary_search(tlist, tdigit, rbin):
    tbin = ''
    zero = []
    none_zero = []
    zero_cnt, none_zero_cnt = 0, 0
    tdigit -= 1
    
    # divide less or much by binary
    for i in tlist:
        tbin = dec2bin(i, max_digit)
        if tbin[tdigit] == '0':
            zero.append(i)
            zero_cnt += 1
        else:
            none_zero.append(i)
            none_zero_cnt += 1
    
    # get lack number binary string
    if zero_cnt <= none_zero_cnt:
        rbin += '0'
        if zero_cnt == 0:
            return int(rbin[::-1], 2)
        return lacking_binary_search(zero, tdigit, rbin)
    else:
        rbin += '1'
        if none_zero_cnt == 0:
            return int(rbin[::-1], 2)
        return lacking_binary_search(none_zero, tdigit, rbin)

def dec2bin(dec, digit):
    bin = ''
    while (digit > 0):
        bin += str(dec % 2)
        dec = int(dec / 2)
        digit -= 1
    return bin[::-1]

if __name__ == '__main__':
    r = main()
    if r == ERROR:
        print "NG NG NG"

実行結果。

input  : [5, 8, 0, 9, 4, 3, 1, 7, 6]
lack number :  2