FilesExpand file tree

master

/

binary_search.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (52 loc) · 1.41 KB

master

/

binary_search.py

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (52 loc) · 1.41 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

Author: OMKAR PATHAK

Created On: 1st August 2017

- Best O(1)

- Average O(logn)

- Worst O(logn)

"""

from __future__ import division

import inspect

def search(_list, target):

"""

This function performs a binary search

on a sorted list and returns the index

of item if successful else returns False

:param _list: list to search

:param target: item to search for

:return: index of item if successful else returns False

"""

if type(_list) is not list:

raise TypeError("binary search only excepts lists, not {}".format(str(type(_list))))

# First position of the list

left = 0

# Last position of the list

right = len(_list) - 1

try:

# you can also write while True condition

while left <= right:

mid = (left + right) // 2

if target == _list[mid]:

return mid

elif target < _list[mid]:

right = mid - 1

else:

left = mid + 1

return False

except TypeError:

return False

# TODO: Are these necessary?

def time_complexities():

"""

Return information on functions

time complexity

:return: string

"""

return "Best Case: O(1), Average Case: O(logn), Worst Case: O(logn)"

def get_code():

"""

easily retrieve the source code

of the function

:return: source code

"""

return inspect.getsource(search)