二分查找法,有相同元素列表,通过指定返回第一个或最后一个元素的索引，得到需要的index(与mysql的InnoDB存储引擎中，指定where条件的>,>=,<,<=比较类似)

binary_search_no_repeating_elements.py

#!/usr/bin/env python
# -*- #coding:utf-8
'''
Created on 2013-9-4
 
@author: mingdong.li
 
二分查找法,作用于没有重复元素的序列的二分查找法,使用循环(递归的调用存在着压栈、出栈的开销，效率比较低。)
'''
 
def binarySearchTemplate(sequence, fromIndex, toIndex, key):
    """
    @param sequence: is a list or tuple to be searched, it's sequential and no repeating elements
    @param fromIndex: the index of the first element to be searched
    @param toIndex: the index of the last element to be searched
    @param key: the value to be searched for
    @return: index of the search key, no found will return -1
    """
    low = fromIndex
    high = toIndex - 1
    while(low <= high):
        mid = low + ((high-low)>>1)
        midValue = sequence[mid]
        
        if midValue < key:
            low = mid + 1
        elif midValue > key:
            high = mid -1
        else:
            return mid
    else:
        return -1
 
def binarySearchArea(sequence, fromIndex, toIndex, key):
    if not isinstance(sequence, list) and not isinstance(sequence, tuple):
        return "The %s is not list or tuple" % sequence
    if fromIndex < 0 or toIndex < 0 or fromIndex >= toIndex:
        return -1
    return binarySearchTemplate(sequence, fromIndex, toIndex, key)
 
def binarySearch(sequence, key):
    if not isinstance(sequence, list) and not isinstance(sequence, tuple):
        return "The %s is not list or tuple" % sequence
    return binarySearchTemplate(sequence, 0, len(sequence), key) 
 
def test():
    a = [23, 35, 45, 56, 78, 79, 80, 90, 100]
    b = [1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7]
    c = (1, 2,(1, 2), 3, 5, 6)
    d = []
    print binarySearch(a, 79)
    print binarySearch(b, 4) # return the index of first found
    print binarySearch(c, (1, 2))
    print binarySearch(d, 11)
    print binarySearchArea(a, 3, 6, 79)
    print binarySearchArea(a, 0, 0, 79)
    print 'end'
 
if __name__ == '__main__':
    print "test..."
    test()

binary_search_same_elements.py

#!/usr/bin/env python
# -*- #coding:utf-8
'''
Created on 2013-9-4
 
@author: mingdong.li
 
二分查找法,有相同元素列表,通过指定返回第一个或最后一个元素的索引，得到需要的index
'''
 
_searchMode = {"FIRST":1, "LAST":0}
 
def binarySearchTemplate(sequence, fromIndex, toIndex, key, searchMode):
    """
    @param sequence: is a list or tuple to be searched, it's sequential and no repeating elements
    @param fromIndex: the index of the first element to be searched
    @param toIndex: the index of the last element to be searched
    @param key: the value to be searched for
    @param searchMode: FIRST=1(return the index of the first element in the repeating sequence); LAST=0(the last one) 
    @return: index of the search key, no found will return -1
    """
    low = fromIndex
    high = toIndex - 1
    flag = -1
    while(low <= high):
        mid = low + ((high-low)>>1)
        midValue = sequence[mid]
        if midValue < key:
            low = mid + 1
        elif midValue > key:
            high = mid -1
        else:
            if searchMode is None:
                return mid
            elif searchMode == _searchMode['FIRST']:
                high = mid - 1
                flag = mid
            elif searchMode == _searchMode['LAST']:
                low = mid + 1
                flag = mid
    else:
        if searchMode == _searchMode['FIRST']:
            if key == sequence[high]:
                return high
            else:
                return flag
        elif searchMode == _searchMode['LAST']:
            if key == sequence[low-1]:
                return low-1
            else:
                return flag
        else:
            return -1
 
def binarySearch(sequence, key, searchMode=None):
    if not isinstance(sequence, list) and not isinstance(sequence, tuple):
        return "The %s is not list or tuple" % sequence
    return binarySearchTemplate(sequence, 0, len(sequence), key, searchMode) 

test_binary_search_same_elements.py

'''
Created on 2013-9-9
 
@author: mingdong.li
'''
import unittest
from sort_algorithm.binary_search_same_elements import binarySearch, _searchMode
from test.test_bisect import TestErrorHandling
from test import test_support
 
class TestBinarySearch(unittest.TestCase):
        a = [1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7]
        b = (1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7)
        precomputedCase = [
            (binarySearch, 'a', 88, None, "The a is not list or tuple"),
            (binarySearch, a, 2, None, 3),
            (binarySearch, a, 88, None, -1),
            (binarySearch, a, 7, _searchMode['FIRST'], 11),
            (binarySearch, a, 7, _searchMode['LAST'], 15),
            (binarySearch, a, 1, _searchMode['FIRST'], 0),
            (binarySearch, a, 1, _searchMode['LAST'], 2),
            (binarySearch, a, 4, _searchMode['FIRST'], 6),
            (binarySearch, a, 11, _searchMode['FIRST'], -1),
            (binarySearch, a, 11, _searchMode['LAST'], -1),
            
            (binarySearch, b, 2, None, 4),
            (binarySearch, b, 88, None, -1),
            (binarySearch, b, 7, _searchMode['FIRST'], 11),
            (binarySearch, b, 7, _searchMode['LAST'], 12),
            (binarySearch, b, 1, _searchMode['FIRST'], 0),
            (binarySearch, b, 1, _searchMode['LAST'], 2),
            (binarySearch, b, 4, _searchMode['FIRST'], 6),
            (binarySearch, b, 11, _searchMode['FIRST'], -1),
            (binarySearch, b, 11, _searchMode['LAST'], -1)
        ]
        
        def test_precomputed(self):
            for func, sequ, key, mode, expected in self.precomputedCase:
                self.assertEqual(func(sequ, key, mode), expected)
 
if __name__ == "__main__":
    from types import BuiltinFunctionType
    test_classes = [TestBinarySearch]
    if isinstance(binarySearch, BuiltinFunctionType):
        test_classes.append(TestErrorHandling)
    
    test_support.run_unittest(*test_classes)
    unittest.main()