关于用 c 语言实现二进制搜索算法的一个查询

Question

In Binary Search Algorithm,

in general

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

But I've just modified the algorithm like these

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

But my teacher told me that the standard algorithm for binary search is the first one and what you have written is also a search algorithm but it's not an algorithm for binary search. Is he correct?.

转载于:https://stackoverflow.com/questions/53058133/a-query-regarding-the-algorithm-of-binary-search-using-c

Answer 1

I think you picked it up wrongly .

The basic Binary Search Algorithm's workflow:

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

Here you can see what actually midPoint = lowerBound + ( upperBound - lowerBound ) / 2 , lowerBound = midPoint + 1 and upperBound = midPoint - 1 does .