FilesExpand file tree

master

/

exponential_search.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

74 lines (56 loc) · 1.81 KB

master

/

exponential_search.py

Copy path

Top

File metadata and controls

• Code
• Blame

74 lines (56 loc) · 1.81 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

64

65

66

67

68

69

70

71

72

73

74

"""

Author: OMKAR PATHAK

Created On: 26th August 2017

- Best O(1)

- Average O(logn)

- Worst O(logn)

More info: https://en.wikipedia.org/wiki/Exponential_search

"""

from __future__ import division

import inspect

def binary_search(_list, left, right, target):

if right >= left:

mid = (left + right) // 2

# if element is present at the mid itself

if _list[mid] == target:

return mid

# If the element is smaller than mid, then it

# can only be present in the left subarray

if _list[mid] > target:

return binary_search(_list, left, mid - 1, target)

# Else the element can only be present in the right

return binary_search(_list, mid + 1, right, target)

return False

def search(_list, target):

"""

This function performs a exponential 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("Exponential search only excepts lists, not {}".format(str(type(_list))))

# is target is at the first position itself

if _list[0] == target:

return 0

# Find range for binary seaarch by repeated doubling

i = 1

while i < len(_list) and _list[i] <= target:

i = i * 2

return binary_search(_list, i//2, min(i, len(_list)), target)

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)