File: BinarySearch.py

package info (click to toggle)
sumo 0.28.0+dfsg1-1~bpo8+1
  • links: PTS, VCS
  • area: main
  • in suites: jessie-backports
  • size: 103,616 kB
  • sloc: xml: 534,021; cpp: 183,697; python: 66,271; java: 43,017; ansic: 36,466; sh: 11,391; makefile: 1,411; perl: 450
file content (70 lines) | stat: -rw-r--r-- 2,186 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#!/usr/bin/env python
# -*- coding: Latin-1 -*-
"""
@file    BinarySearch.py
@author  Sascha Krieg
@author  Daniel Krajzewicz
@author  Michael Behrisch
@date    2008-04-01
@version $Id: BinarySearch.py 20433 2016-04-13 08:00:14Z behrisch $

binary search helper functions.

SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
Copyright (C) 2008-2016 DLR (http://www.dlr.de/) and contributors

This file is part of SUMO.
SUMO is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
"""


def isElmInList(list, elm):
    maxindex = len(list) - 1
    index = 0
    while index <= maxindex:
        middle = index + ((maxindex - index) / 2)
        if list[middle] == elm:  # if elm is found
            return True
        elif elm < list[middle]:
            maxindex = middle - 1
        else:
            index = middle + 1
    return False


def isElmInListFaster(list, elm):
    """Interpolation search only for integers :-("""

    links = 0
    # linke Teilfeldbegrenzung
    rechts = len(list) - 1
    # rechte Teilfeldbegrenzung
    versch = 0
    # Anzahl verschiedener Elemente
    pos = 0
    # aktuelle Teilungsposition

    # solange der Schluessel im Bereich liegt (andernfalls ist das gesuchte
    # Element nicht vorhanden)
    while elm >= list[links] and elm <= list[rechts]:
        # Aktualisierung der Anzahl der verschiedenen Elemente
        versch = list[rechts] - list[links]

        # Berechnung der neuen interpolierten Teilungsposition
        pos = links + \
            int(((rechts - links + 0.0) * (elm - list[links]) / versch))

        if elm > list[pos]:             # rechtes Teilintervall
            links = pos + 1
            # daten[pos] bereits ueberprueft
        elif elm < list[pos]:        # linkes Teilintervall
            rechts = pos - 1
            # daten[pos] bereits ueberprueft
        else:                                     # Element gefunden
            return True
            # Position zurueckgeben
    return False
    # Element nicht gefunden