| 53 | """ |
| 54 | class Solution(object): |
| 55 | def binarySearch(self, rawList, target, index=0): |
| 56 | |
| 57 | if target >= rawList[-1]: |
| 58 | return len(rawList) - 1 |
| 59 | |
| 60 | if target < rawList[0]: |
| 61 | return -1 |
| 62 | |
| 63 | split = len(rawList) // 2 |
| 64 | |
| 65 | leftList = rawList[:split] |
| 66 | rightList = rawList[split:] |
| 67 | |
| 68 | |
| 69 | if leftList[-1] <= target and rightList[0] > target: |
| 70 | return len(leftList) + index - 1 |
| 71 | |
| 72 | if rightList[0] == target: |
| 73 | return len(leftList) + index |
| 74 | |
| 75 | if leftList[-1] > target: |
| 76 | return self.binarySearch(leftList, target, index=index) |
| 77 | |
| 78 | if rightList[0] < target: |
| 79 | return self.binarySearch(rightList, target, index=index+len(leftList)) |
| 80 | |
| 81 | def binarySearch2(self, rawList, target): |
| 82 | split = len(rawList) // 2 |