leetcode/033.py at master · lwxted/leetcode · GitHub

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
class Solution(object):
  def _searchRecursive(self, nums, target, st, ed):
    if st == ed:
      return -1
    if ed - st == 1:
      return st if nums[st] == target else -1
    mid = (st + ed) / 2
    if nums[mid] == target:
      return mid
    elif nums[mid] < target:
      r = self._searchRecursive(nums, target, mid, ed)
      if r != -1:
        return r
      return self._searchRecursive(nums, target, st, mid)
    else:
      l = self._searchRecursive(nums, target, st, mid)
      if l != -1:
        return l
      return self._searchRecursive(nums, target, mid, ed)

  def search(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    return self._searchRecursive(nums, target, 0, len(nums))

print Solution().search([0], 2)