How many elements would have to be looked to locate these elements?

[dseals22]

How many elements would have to be looked (binary search) at in order to find an integer 5000 at element 499 and an integer 7282 at element 686 assuming it's binary search algorithm and total number of elements in the array are 1000?

I do have a theory though (see my theory below:)

1000/2= the first element is 500 element

500/2 the next element is 250 element.

[dseals22]

Do you think you can help me @weaknessforcats?

[Frinavale]

You seem to know what you are doing.

The theory behind a binary search is that you are looking within an ascending sorted list and you search for it by cutting the list in half to check to see if it is the value you are looking for...if it's not you check to see if the if the value you are looking for is higher or lower than what you landed at and cut that half of the list in half and do it again.

A basic binary search algorithm is pretty much as follows:

1. Set LeftPosition to 0 and RightPosition to the number of items int the array − 1.
2. If LeftPosition > RightPosition, the search terminates as unsuccessful because your list is empty or you have searched through the whole array.
3. Set MidPoint (the position of the middle element) to the floor (the largest previous integer) of (LeftPostition + RightPostion) / 2.
   • If ValueAtTheMidPointPostitionInTheArray < WhatYouAreLookingFor, set LeftPostion to MidPoint + 1 and go to step 2.
   • If ValueAtTheMidPointPostitionInTheArray> WhatYouAreLookingFor, set RightPosition to MidPoint − 1 and go to step 2.
4. Now ValueAtTheMidPointPostitionInTheArray= WhatYouAreLookingFor, the search is done; return MidPoint.

The Big-O notation for the worst case (when you don't find anything) is O(log n) because you are constantly dividing the list in half and so the operations required to complete the search decrease with each iteration.

You should step through the algorithm and draw out your trees to figure out how many iterations it takes to get to each element-position that you are looking for.

Your first search tree(search for index 499) looks something like:

            (1000)
            /    \            
       (0-500)   (501-999)
      /     \
(0-250)  (251-500)
          /      \
  (251-375)      (376-500)
                 /      \
          (376-438)    (439-500)
                        /     \
                 (438-469)   (470-500)
                             /      \
                       (469-485)   (486-500)
                                   /    \
                            (485-493)  (494-500)
                                        /    \
                                 (493-497) (498-500)
                                            /   \
                                         (499)  (500)
                                          |
                                       (found)