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? — Hearen
– Hearen, Commented Oct 30, 2018 at 5: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
– vishal-wadhwa, Commented Oct 30, 2018 at 5: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
– Md. Mokammal Hossen Farnan, Commented Oct 30, 2018 at 5:56
The difference is that the first one reduces the range by one more than your algorithm does, and therefore potentially finish faster. — Surt
– Surt, Commented Oct 30, 2018 at 6:31
One difference is that, if you're not careful, the second one can easily get into an infinite loop . . . — ruakh
– ruakh, Commented Oct 30, 2018 at 7:15

RahulV · Accepted Answer · 2018-10-30 07:32:31Z

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, 2018 at 7:32

RahulV

92 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Siva Nagendra Kumar Vepada Over a year ago

Actually in my algorithm high is initiated by length of the list

Md. Mokammal Hossen Farnan · Accepted Answer · 2018-10-30 06:02:33Z

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 .

Collectives™ on Stack Overflow

A query regarding the algorithm of binary search using C

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related