Блог

Я пытаюсь разработать рекурсивный алгоритм двоичного поиска (в псевдокоде), чтобы найти произвольное число k в (отсортированном) списке из n целых чисел, который разбивает экземпляр на две части: одну с 1/3 элементов, а другую с 2/3. Затем мне нужно сравнить его сложность с более традиционным алгоритмом двоичного поиска, который разбивает экземпляры на половины.

Пока что вот что я придумал с точки зрения псевдокода — я не уверен, правильно ли это. Однако я не слишком уверен в том, как я могу сравнить их временную сложность.

   BinarySearch(A, value, low, high) {
      // invariants: value > A[i] for all i < low
                     value < A[i] for all i > high
      if (high < low)
          return not_found // value would be inserted at index "low"
      third = (low   high) / 3
      if (A[third] > value)
          return BinarySearch(A, value, low, third-1)
      else if (A[third] < value)
          return BinarySearch(A, value, third 1, high)
      else
          return third
  }
  

Прежде всего, third = (low high) / 3 это просто неправильно. Если, например, low == 100 и high == 110 , вы получите third == 70 . Не совсем то, что вам нужно.

Правильное разделение third = low (high - low)/3 .

Что касается сложности, подумайте о наихудшем случае, в котором целевое число равно максимальному (которое всегда находится в большем разделе). Как пространство поиска сокращает уровень рекурсии paer?