Запрос относительно алгоритма бинарного поиска с использованием C

Question

В Binary Search Algorithm,

в целом

if   mid_value > search_element we set high = mid_pos-1 ;
else mid_value < search_element we set  low = mid_pos+1 ;

Но я только что изменил алгоритм, как эти

if   mid_value > search_element we set high = mid_pos ;
else mid_value < search_element we set  low = mid_pos ;

Но мой учитель сказал мне, что стандартный алгоритм для binary search является первым и то, что вы написали, также является алгоритмом поиска, но это не алгоритм бинарного поиска. Он прав?

Answer 1

Ваш алгоритм неверен:

чехол: list [1, 2], searchElem = 2, low = 0, high = 1

средний = (низкий + высокий) / 2 = (0 + 1) / 2 = 0

mid

так что вы получите бесконечный цикл.

Answer 2

Я думаю, вы ошиблись.

Основной рабочий процесс Binary Search Algorithm:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.

      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

      if A[midPoint] < x
         set lowerBound = midPoint + 1

      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while

end procedure

Здесь вы можете увидеть, что на самом деле midPoint = lowerBound + ( upperBound - lowerBound ) / 2, lowerBound = midPoint + 1 и upperBound = midPoint - 1 делает.