468,146 Members | 1,537 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,146 developers. It's quick & easy.

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

74 64KB
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.
Sep 8 '17 #1

✓ answered by 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:
Expand|Select|Wrap|Line Numbers
  1.             (1000)
  2.             /    \            
  3.        (0-500)   (501-999)
  4.       /     \
  5. (0-250)  (251-500)
  6.           /      \
  7.   (251-375)      (376-500)
  8.                  /      \
  9.           (376-438)    (439-500)
  10.                         /     \
  11.                  (438-469)   (470-500)
  12.                              /      \
  13.                        (469-485)   (486-500)
  14.                                    /    \
  15.                             (485-493)  (494-500)
  16.                                         /    \
  17.                                  (493-497) (498-500)
  18.                                             /   \
  19.                                          (499)  (500)
  20.                                           |
  21.                                        (found)
  22.  

2 3434
dseals22
74 64KB
Do you think you can help me @weaknessforcats?
Sep 8 '17 #2
Frinavale
9,735 Expert Mod 8TB
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:
Expand|Select|Wrap|Line Numbers
  1.             (1000)
  2.             /    \            
  3.        (0-500)   (501-999)
  4.       /     \
  5. (0-250)  (251-500)
  6.           /      \
  7.   (251-375)      (376-500)
  8.                  /      \
  9.           (376-438)    (439-500)
  10.                         /     \
  11.                  (438-469)   (470-500)
  12.                              /      \
  13.                        (469-485)   (486-500)
  14.                                    /    \
  15.                             (485-493)  (494-500)
  16.                                         /    \
  17.                                  (493-497) (498-500)
  18.                                             /   \
  19.                                          (499)  (500)
  20.                                           |
  21.                                        (found)
  22.  
Sep 11 '17 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

1 post views Thread by lltaylor2000 | last post: by
25 posts views Thread by Dave | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.