0

I am working on the binary search project in pset 3. I want to specify that if the sought value is greater than the middle value of the sorted array, that the function should then only look in the section of the array that between the middle value and the upper limit value. In other words, how do you specify an array segment/section? I couldn't find an answer to this anywhere.

Below I have included some of my code, I am trying to specify the first half and second half of the array. I believe that in python you can achieve this by using something like array[3:8] to get values from array[3] to array[7]?

int L=n;
while (L>0)
{
    if values[L/2]==value
        return true;
    if values[L/2]<value
        L= (**second half of values[]**);
    if values[L/s]>value
        L= (**first half of values[]**);
}
2
  • what about keeping track of the minimum and maximum indices? see youtu.be/D5SrAga1pno! – kzidane Oct 25 '15 at 9:29
  • i am not sure there is an easy way to find the range. What I did was figured out the math of finding the middle of two numbers and hard coded that formula. For example half way between 3 and 8; int Min = 3, int Max = 8. Int Mid = (Max + Min)/2; I know this 5.5 but because it is an int it will be 5. So that will get you values[5]. If I was you I would check the min, mid, and max because the value you are looking for maybe at values[0]. If it is not then make your mid the new max if values[ ] is less than mid and find the new mid and check min,mid,max values again. You can go the other way also. – A. Acosta Oct 26 '15 at 2:16
0

I'm not sure if you can do what you want, or how to do it. As A.Acosta recommends, what i did is create a new array with either the first half or the second one of the original array and call again the search function on this new array, recursively. In pseudo code it could be something like:

int half = n/2;

if values[half] == value
    return true;

else
    if values[half] > value
        calculate the number of elements in the first half of values
        create anew array and populate it with the first half of values
        call search again with the new array instead of the original \ 
            values and the new size instead of the original n
        return the result of search
    else if values[half] < value
        calculate the number of elements in the second half of values
        create anew array and populate it with the second half of values
        call search again with the new array instead of the original \
            values and the new size instead of the original n
        return the result of search
1
  • Thanks for accepting the answer! – Marti Serra Oct 29 '15 at 12:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .