Given a sortedList and value x, return the index i where sortedList[i-1] <= x < sortedList[i] Which means, sortedList.insert( findIndex(sortedList, x), x ) will give a sorted list
(sortedList, x, indexBuffer=0)
| 38 | |
| 39 | #======================================================================== |
| 40 | def findIndex(sortedList, x, indexBuffer=0): |
| 41 | ''' Given a sortedList and value x, return the index i where |
| 42 | sortedList[i-1] <= x < sortedList[i] |
| 43 | |
| 44 | Which means, |
| 45 | sortedList.insert( findIndex(sortedList, x), x ) |
| 46 | will give a sorted list |
| 47 | ''' |
| 48 | |
| 49 | if len(sortedList)==2: |
| 50 | |
| 51 | if x==sortedList[-1]: return indexBuffer+2 |
| 52 | elif x>=sortedList[0]: return indexBuffer+1 |
| 53 | |
| 54 | else: |
| 55 | L = len(sortedList) |
| 56 | firstHalf = sortedList[:L/2+1] |
| 57 | secondHalf = sortedList[(L/2):] |
| 58 | |
| 59 | if secondHalf[-1]<=x: |
| 60 | return indexBuffer + len(sortedList) |
| 61 | elif x< firstHalf[0]: |
| 62 | return indexBuffer |
| 63 | else: |
| 64 | if firstHalf[-1] < x: |
| 65 | return findIndex(secondHalf, x, indexBuffer=L/2+indexBuffer) |
| 66 | else: |
| 67 | return findIndex(firstHalf,x, indexBuffer=indexBuffer) |
| 68 | |
| 69 | #======================================================================== |
| 70 | def randomPickList(L): |
no outgoing calls
no test coverage detected