Binary search in C ++ with an array

Here is an array with exactly 15 elements:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Suppose we do a binary search for an element. Indicate any elements that will be found by examining two or less numbers from the array.

What I have: since we are doing a binary search, so the number found by only one comparison will be the 7th element = 7. For two comparisons, this leads to the second division of the array. That is, the found number can be either 3 or 11.

Am I right or not?

+4
source share
2 answers

You are almost right, the first number is not seven, but eight.

The remaining 2 will be equal to 4 and 12.

The correct answer will be 4, 8, 12

+2
source

Κ»I found answer 8, which is the 7th element, the rest of the elements found were the 3.5th and 10.5th elements of the sorted array. So, the following two numbers: 4 and 11.

An explanation of how I received the answers.
this array is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

 head=1 tail=15 middle= 0+14/2=7th element **0 is the index value of 1 and 14 is of 15** middle value turns to be 8 as it is the 7th element. solving value for first half head=1 tail=8 middle= 0+7/2=3.5 or 3rd element **0 is the index value of 1 and 7 is of 8** middle value now turns to be 4 as it is the 3rd element. solving value for second half head=8 tail=15 middle= 7+14/2=10.5 or 10th element **7 is the index value of 8 and 14 is of 15** middle value now turns to be 11 as it is the 10th element of the array` 

Blockquote

0
source

Source: https://habr.com/ru/post/1494096/


All Articles