0
$\begingroup$

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 the total number of elements in the array are 1000? I do know that for the binary search algorithm you have divide the total number of elements that would be in your array(which is 1000) in half and keep doing until you find the desired element! Can someone help me? Please!

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.

$\endgroup$
  • $\begingroup$ where are you having the trouble then, if you have an idea ? $\endgroup$ – user451844 Sep 8 '17 at 1:53
  • $\begingroup$ @Roddy MacPhee i am not sure this right way to approach this problem. $\endgroup$ – DMicheal Sep 8 '17 at 1:55
  • $\begingroup$ so try it and find out ? or look at wikipedia etc. $\endgroup$ – user451844 Sep 8 '17 at 1:55
  • $\begingroup$ @RoddyMacPhee Do you think you can help me? I am just not understanding. I know that 1000 elements would have 0-999 indexes for it, but the approach that I took doesn't make sense. $\endgroup$ – DMicheal Sep 8 '17 at 1:57
  • $\begingroup$ how do you keep stepping that's a start. how would you get to 499th index. $\endgroup$ – user451844 Sep 8 '17 at 2:01
0
$\begingroup$

here's a worked example of roughly how the algorithm works:

[10,20,30,40,50,60,70,80,90,100]

I want to find 70:

I take the rough middle element ( which is 50) I compare it to 70 and:

if 50<70 I take roughly the upper half of the values if 50>70 I take roughly the lower half of the values if 50=70 I am finished

since 50<70 I take roughly the upper half of the values: [60,70,80,90,100] I then take the middle element (80) and compare that to 70 since 80>70 I take roughly the lower half of the values I took before:

[60,70,80] I take the rough middle element ( 70) and compare it to 70 since 70=70 I am now finished.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I understand how you are approaching your own example, but my array is a huger than that! Would I have to create a java program in order to figure out how many elements or comparison would have to be gone through to find those two elements? Can this be done using pen and paper? $\endgroup$ – DMicheal Sep 9 '17 at 14:45
  • $\begingroup$ any element can be found in under $log_2(n)+1$ steps $\endgroup$ – user451844 Sep 9 '17 at 14:47
  • $\begingroup$ Please read above the text I have written. $\endgroup$ – DMicheal Sep 9 '17 at 14:47
  • $\begingroup$ I did for your comment for 1 million elements the worse case scenario is about 20 comparisons. $\endgroup$ – user451844 Sep 9 '17 at 14:50
  • $\begingroup$ So it can be done using an algorithm formula; So if I do logbase 2 of 1000 + 1, I will see the number of comparisons it would have to make? That doesn't make sense to me. $\endgroup$ – DMicheal Sep 9 '17 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.