A query regarding the algorithm of binary search using 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?.

Possible duplicate of [Where can I get a "useful" C++ binary search algorithm?](https://stackoverflow.com/questions/446296/where-can-i-get-a-useful-c-binary-search-algorithm) — Hearen, Oct 30 '18 at 05:51
This is also binary search. It is just that we set the position as (mid-1) or (mid+1) because we do not need to check the middle element again in the next condition because it was already done in the previous one. The runtime is more or less the same in either case. — vishal-wadhwa, Oct 30 '18 at 05:52
Did you know , what actually mean by high = mid_pos-1 ,low= mid_pos+1 ? . Please, first understand the basic structure and flow of position . — Md. Mokammal Hossen Farnan, Oct 30 '18 at 05:56
The difference is that the first one reduces the range by one more than your algorithm does, and therefore potentially finish faster. — Surt, Oct 30 '18 at 06:31
One difference is that, if you're not careful, the second one can easily get into an infinite loop . . . — ruakh, Oct 30 '18 at 07:15

score 1 · Answer 1 · answered Oct 30 '18 at 07:32

1

Your Algo is not correct :

case : list [1, 2] , searchElem = 2 , low = 0,high = 1

mid = (low+high)/2 = (0+1)/2 = 0

mid < searchElem set low = mid updated mid = 0, high = 1 [list didn't change]

so you will end up with infinite loop.

answered Oct 30 '18 at 07:32

RahulV

19
2

Actually in my algorithm high is initiated by length of the list – Siva Nagendra Kumar Vepada Oct 30 '18 at 16:54

score 0 · Answer 2 · answered Oct 30 '18 at 06:02

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 .

A query regarding the algorithm of binary search using C

2 Answers2