Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 679b34f

Browse files
author
Muh. Angga Muttaqien
committed
add binary search
1 parent b0de76e commit 679b34f

File tree

1 file changed

+55
-0
lines changed

1 file changed

+55
-0
lines changed

‎searching/binary-search.py

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
2+
def binary_search(sorted_collection, item):
3+
4+
left = 0
5+
right = len(sorted_collection) -1
6+
7+
while left <= right:
8+
midpoint = (left + right) // 2
9+
current_item = sorted_collection[midpoint]
10+
if current_item == item:
11+
return midpoint
12+
else:
13+
if item < current_item:
14+
right = midpoint - 1
15+
else:
16+
left = midpoint + 1
17+
18+
return None
19+
20+
21+
def __assert_sorted(collection):
22+
23+
if collection != sorted(collection):
24+
raise ValueError('Collection must be sorted')
25+
26+
return True
27+
28+
29+
def main():
30+
print("=== Binary Search (Algorithm) - A half-interval search, logarithmic search, or binary search that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array")
31+
32+
import sys
33+
34+
user_input = raw_input("Enter numbers separated by a comma: ")
35+
collection = [int(item) for item in user_input.split(',')]
36+
37+
try:
38+
__assert_sorted(collection)
39+
except ValueError:
40+
sys.exit('Sequence must be sorted to apply binary search')
41+
42+
43+
target_input = input("Enter single number to be found in the list: ")
44+
target = int(target_input)
45+
46+
result = binary_search(collection, target)
47+
48+
if result is not None:
49+
print("{} found at position: {}".format(target, result))
50+
else:
51+
print("Not found")
52+
53+
54+
if __name__=='__main__':
55+
main()

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /