Python-Programs/ordered_binary_search.py at master · anumsh/Python-Programs · GitHub

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
defOrdered_binary_Search(olist, item):

iflen(olist) ==0:
returnFalse
else:
midpoint=len(olist) //2
ifolist[midpoint] ==item:
returnTrue
else:
ifitem<olist[midpoint]:
returnbinarySearch(olist[:midpoint], item)
else:
returnbinarySearch(olist[midpoint+1:], item)

defbinarySearch(alist, item):

first=0
last=len(alist) -1
found=False

whilefirst<=lastandnotfound:
midpoint= (first+last) //2
ifalist[midpoint] ==item:
found=True
else:
ifitem<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1

returnfound

print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))
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
defOrdered_binary_Search(olist, item):

iflen(olist) ==0:
returnFalse
else:
midpoint=len(olist) //2
ifolist[midpoint] ==item:
returnTrue
else:
ifitem<olist[midpoint]:
returnbinarySearch(olist[:midpoint], item)
else:
returnbinarySearch(olist[midpoint+1:], item)

defbinarySearch(alist, item):

first=0
last=len(alist) -1
found=False

whilefirst<=lastandnotfound:
midpoint= (first+last) //2
ifalist[midpoint] ==item:
found=True
else:
ifitem<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1

returnfound

print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))
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
defOrdered_binary_Search(olist, item):

iflen(olist) ==0:
returnFalse
else:
midpoint=len(olist) //2
ifolist[midpoint] ==item:
returnTrue
else:
ifitem<olist[midpoint]:
returnbinarySearch(olist[:midpoint], item)
else:
returnbinarySearch(olist[midpoint+1:], item)

defbinarySearch(alist, item):

first=0
last=len(alist) -1
found=False

whilefirst<=lastandnotfound:
midpoint= (first+last) //2
ifalist[midpoint] ==item:
found=True
else:
ifitem<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1

returnfound

print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))
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
defOrdered_binary_Search(olist, item):

iflen(olist) ==0:
returnFalse
else:
midpoint=len(olist) //2
ifolist[midpoint] ==item:
returnTrue
else:
ifitem<olist[midpoint]:
returnbinarySearch(olist[:midpoint], item)
else:
returnbinarySearch(olist[midpoint+1:], item)

defbinarySearch(alist, item):

first=0
last=len(alist) -1
found=False

whilefirst<=lastandnotfound:
midpoint= (first+last) //2
ifalist[midpoint] ==item:
found=True
else:
ifitem<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1

returnfound

print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))
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
defOrdered_binary_Search(olist, item):

iflen(olist) ==0:
returnFalse
else:
midpoint=len(olist) //2
ifolist[midpoint] ==item:
returnTrue
else:
ifitem<olist[midpoint]:
returnbinarySearch(olist[:midpoint], item)
else:
returnbinarySearch(olist[midpoint+1:], item)

defbinarySearch(alist, item):

first=0
last=len(alist) -1
found=False

whilefirst<=lastandnotfound:
midpoint= (first+last) //2
ifalist[midpoint] ==item:
found=True
else:
ifitem<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1

returnfound

print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))
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
defOrdered_binary_Search(olist, item):

iflen(olist) ==0:
returnFalse
else:
midpoint=len(olist) //2
ifolist[midpoint] ==item:
returnTrue
else:
ifitem<olist[midpoint]:
returnbinarySearch(olist[:midpoint], item)
else:
returnbinarySearch(olist[midpoint+1:], item)

defbinarySearch(alist, item):

first=0
last=len(alist) -1
found=False

whilefirst<=lastandnotfound:
midpoint= (first+last) //2
ifalist[midpoint] ==item:
found=True
else:
ifitem<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1

returnfound

print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))
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
defOrdered_binary_Search(olist, item):

iflen(olist) ==0:
returnFalse
else:
midpoint=len(olist) //2
ifolist[midpoint] ==item:
returnTrue
else:
ifitem<olist[midpoint]:
returnbinarySearch(olist[:midpoint], item)
else:
returnbinarySearch(olist[midpoint+1:], item)

defbinarySearch(alist, item):

first=0
last=len(alist) -1
found=False

whilefirst<=lastandnotfound:
midpoint= (first+last) //2
ifalist[midpoint] ==item:
found=True
else:
ifitem<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1

returnfound

print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))
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
defOrdered_binary_Search(olist, item):

iflen(olist) ==0:
returnFalse
else:
midpoint=len(olist) //2
ifolist[midpoint] ==item:
returnTrue
else:
ifitem<olist[midpoint]:
returnbinarySearch(olist[:midpoint], item)
else:
returnbinarySearch(olist[midpoint+1:], item)

defbinarySearch(alist, item):

first=0
last=len(alist) -1
found=False

whilefirst<=lastandnotfound:
midpoint= (first+last) //2
ifalist[midpoint] ==item:
found=True
else:
ifitem<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1

returnfound

print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))