iframe-proxy | Sunbelt Computer Software

History

161 lines (121 loc) · 4.38 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

"""

This is pure python implementation of binary search algorithm

For doctests run following command:

python -m doctest -v binary_search.py

python3 -m doctest -v binary_search.py

For manual testing run:

python binary_search.py

"""

from __future__ import print_function

import bisect

try:

raw_input # Python 2

except NameError:

raw_input = input # Python 3

def binary_search(sorted_collection, item):

"""Pure implementation of binary search algorithm in Python

Be careful collection must be sorted, otherwise result will be

unpredictable

:param sorted_collection: some sorted collection with comparable items

:param item: item value to search

:return: index of found item or None if item is not found

Examples:

>>> binary_search([0, 5, 7, 10, 15], 0)

>>> binary_search([0, 5, 7, 10, 15], 15)

>>> binary_search([0, 5, 7, 10, 15], 5)

>>> binary_search([0, 5, 7, 10, 15], 6)

"""

left = 0

right = len(sorted_collection) - 1

while left <= right:

midpoint = (left + right) // 2

current_item = sorted_collection[midpoint]

if current_item == item:

return midpoint

else:

if item < current_item:

right = midpoint - 1

else:

left = midpoint + 1

return None

def binary_search_std_lib(sorted_collection, item):

"""Pure implementation of binary search algorithm in Python using stdlib

Be careful collection must be sorted, otherwise result will be

unpredictable

:param sorted_collection: some sorted collection with comparable items

:param item: item value to search

:return: index of found item or None if item is not found

Examples:

>>> binary_search_std_lib([0, 5, 7, 10, 15], 0)

>>> binary_search_std_lib([0, 5, 7, 10, 15], 15)

>>> binary_search_std_lib([0, 5, 7, 10, 15], 5)

>>> binary_search_std_lib([0, 5, 7, 10, 15], 6)

"""

index = bisect.bisect_left(sorted_collection, item)

if index != len(sorted_collection) and sorted_collection[index] == item:

return index

return None

def binary_search_by_recursion(sorted_collection, item, left, right):

"""Pure implementation of binary search algorithm in Python by recursion

Be careful collection must be sorted, otherwise result will be

unpredictable

First recursion should be started with left=0 and right=(len(sorted_collection)-1)

:param sorted_collection: some sorted collection with comparable items

:param item: item value to search

:return: index of found item or None if item is not found

Examples:

>>> binary_search_std_lib([0, 5, 7, 10, 15], 0)

>>> binary_search_std_lib([0, 5, 7, 10, 15], 15)

>>> binary_search_std_lib([0, 5, 7, 10, 15], 5)

>>> binary_search_std_lib([0, 5, 7, 10, 15], 6)

"""

if (right < left):

return None

midpoint = left + (right - left) // 2

if sorted_collection[midpoint] == item:

return midpoint

elif sorted_collection[midpoint] > item:

return binary_search_by_recursion(sorted_collection, item, left, midpoint-1)

else:

return binary_search_by_recursion(sorted_collection, item, midpoint+1, right)

def __assert_sorted(collection):

"""Check if collection is sorted, if not - raises :py:class:`ValueError`

:param collection: collection

:return: True if collection is sorted

:raise: :py:class:`ValueError` if collection is not sorted

Examples:

>>> __assert_sorted([0, 1, 2, 4])

True

>>> __assert_sorted([10, -1, 5])

Traceback (most recent call last):

...

ValueError: Collection must be sorted

"""

if collection != sorted(collection):

raise ValueError('Collection must be sorted')

return True

if __name__ == '__main__':

import sys

user_input = raw_input('Enter numbers separated by comma:\n').strip()

collection = [int(item) for item in user_input.split(',')]

try:

__assert_sorted(collection)

except ValueError:

sys.exit('Sequence must be sorted to apply binary search')

target_input = raw_input('Enter a single number to be found in the list:\n')

target = int(target_input)

result = binary_search(collection, target)

if result is not None:

print('{} found at positions: {}'.format(target, result))

else:

print('Not found')

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

binary_search.py

Latest commit

History

binary_search.py

File metadata and controls