FilesExpand file tree

 master

/

binary_search.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

executable file

·

65 lines (50 loc) · 1.32 KB

 master

/

binary_search.py

Copy path

Top

File metadata and controls

• Code
• Blame

executable file

·

65 lines (50 loc) · 1.32 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

#!/usr/bin/python

"""

Given a sorted array of integers, return the index of the given element.

ihttp://codekata.com/kata/kata02-karate-chop/

"""

import random

import sys

arr = []

for i in range(20):

arr.append(random.randint(0, 100))

arr = sorted(arr)

print "The array: {0}".format(arr)

print "Enter int to search for:"

key = int(raw_input())

def chop1(key, arr):

low, high = 0, len(arr)

while (low <= high):

mid = (high+low)//2

if arr[mid] == key:

return mid

if arr[mid] < key:

low = mid + 1

else:

high = mid - 1

print chop1(key, arr)

def binsearch_recursive(key, arr, low, high):

if low > high:

return

mid = (low+high)//2

if arr[mid] == key:

return mid

if arr[mid] < key:

return binsearch_recursive(key, arr, mid+1, high)

else:

return binsearch_recursive(key, arr, low, mid-1)

def chop2(key, arr):

return binsearch_recursive(key, arr, 0, len(arr))

print chop2(key, arr)

def chop3(key, arr):

low, high = 0, len(arr)

# Reduce search space until high and low are two consecutive elements

while (high - low > 1):

mid = (low+high)//2

if arr[mid] <= key:

low = mid

else:

high = mid

if arr[low] == key:

return low

print chop3(key, arr)