CODEWITHSUNDEEP
searchtheorybinary-search
Rasmus
Rasmus

Reputation: 241

Binary Search and duplicates

Let's say we an array {–2, 8, 13, 22, 25, 25, 38, 42, 51, 103}

When a binary search splits it in 2 the first time, what will be considered the middle value?

My own guess is the second value named 25, because only then the search knows that it's identical.

Upvotes: 0

Views: 69

Answers (2)

Ciprian
Ciprian

Reputation: 31

The middle value is first 25 number.

Your binarySearch first call is something like that : binarySearch(a,1,a.length) , where "a" is your array.

Your array length is 10 , so m = ((10-1) +1)/2 = 5 position in array .

Then you call binarySearch(1,m) and apply the same method to this array (the first half from orginal array ) –2, 8, 13, 22, 25

Upvotes: 1

Aninda Bhattacharyya
Aninda Bhattacharyya

Reputation: 1251

I believe it always tries to find the middle by 

(0+n)/2 = (0+9)/2 = 4(Integer)

In your case.

So in case you want to search 25 itself, as per the algorithm you will find in the lower bound group, position 4 first as a match.

Upvotes: 1

Related Questions