searching for a number in a list

Hi, I made a code below which I need to use to find a value in a list L. Supposing I have the following list L = [1 3 5 9 2 4 0 8]. If I call searchForIt(L, 2) I should get 5. But this is not what happens in matlab. I can't seem to figure out why that is.

function [Ind] = searchForIt(L, num)
% Ind = index of first occurence (if any) of num in L
% L is a list of numbers that is unsorted
% num is the number I am looking for in the list
Ind = [];
left_Ind = 1;
right_Ind = length(L);
while right_Ind > left_Ind;
    mid_Ind = floor((left_Ind + right_Ind)/2);
    if L(mid_Ind) == num;
    elseif L(mid_Ind) < num;
        left_Ind = mid_Ind + 1;
    else right_Ind = mid_Ind - 1;
    end
    end
end

Answer 1

[Walter Roberson]

That is code for a binary search, which requires that the list L be sorted already. As your list is not sorted, you will not get the answers you expect.

[MG]

Ok I sorted the list:

function [Ind] = searchForIt(L, num)
B = sort(L);
Ind = [];
left_Ind = 1;
right_Ind = length(B);
while right_Ind > left_Ind;
    mid_Ind = floor((left_Ind + right_Ind)/2);
    if B(mid_Ind) == num;
    elseif B(mid_Ind) < num;
        left_Ind = mid_Ind + 1;
    else right_Ind = mid_Ind - 1;
    end
    end
end

But I still don't get the right thing. Why is that?

[Walter Roberson]

if B(mid_Ind) == num then you do not do anything, including not changing left_Ind or right_Ind, so your while loop would run infinitely.

Your code never assigns anything to Ind after the first Ind = []

I would be relatively sure that you want to return the index into the original vector, not the index into the sorted vector.

[MG]

Ok so I fixed that part and did the following:

function Ind = searchForIt(L, num)
% L is a list of unsorted numbers
% num is the value in the list we are seeking
% Ind is index of first occurrence (if any) of num in L
% Sort the list
B = sort(L);
% Initialize Ind
Ind = [];
left_Ind = 1;
right_Ind = length(B);
while right_Ind > left_Ind;
    mid_Ind = floor((left_Ind + right_Ind)/2);
    if B(mid_Ind) == num;
        Ind = mid_Ind;
    elseif B(mid_Ind) < num;
        left_Ind = mid_Ind + 1;
    else right_Ind = mid_Ind - 1;
    end
    end
end

But now matlab runs indefinitely so there is still something wrong. Before I was just getting [] in the command window, but now I don't even get anything. I am following instructions in an assignment, it says in there I have to start with an unsorted list.

[Image Analyst]

Again, why not simply use find() instead of all this overly complicated stuff?

[MG]

I would love to, believe me. But unfortunately I have to stick to assignment instructions and I'm new to matlab so its giving me grief.

[Image Analyst]

Oh, it's homework. You didn't tag it as such. I did so for you.

[Walter Roberson]

When you do

Ind = mid_Ind;

does that change the variables that you use in your while expression?

[MG]

@Image analyst- sorry, I'm new to the site.

@Walter- I am not sure what you mean, sorry. My homework says that in the case of if L(mid Ind)=num then Set Ind=mid_Ind and then Return Ind (which I assumed matlab automatically does?).

[Walter Roberson]

In order to exit a while loop, you need to have changed any variables involved in the controlling expression so that the expression becomes false. Your condition is right_Ind > left_Ind but when you find an exact match you are not changing either right_Ind or left_Ind so on the next iteration it will continue to find the condtion to be true, with go back through, once more assign that value to Ind, leave the left and right ind changed, go back through the condition which will still be true because left and right ind did not change...

There is, however, one way to leave a while loop early. Read about "break".

[MG]

Thank you for the suggestion, the infinite while loop thing is no longer.

The problem is, now I'm back to getting an empty set. The only time I don't get an empty set is if I input L to be [0 1 2 3 4 5 6 7 8 9]. Then I get 3. The updated code is below:

function Ind = searchForIt(L, num)
% L is a list of unsorted numbers
% num is the value in the list we are seeking
% Ind is index of first occurrence (if any) of num in L
% Sort the list
B = sort(L);
% Initialize Ind
Ind = [];
left_Ind = 1;
right_Ind = length(B);
    while right_Ind > left_Ind;
        mid_Ind = floor((left_Ind + right_Ind)/2);
        if B(mid_Ind) == num;
            Ind = mid_Ind;
            break
        elseif B(mid_Ind) < num;
            left_Ind = mid_Ind + 1;
        else right_Ind = mid_Ind - 1;
        end
    end
end

[Walter Roberson]

Left and right ind can become exactly equal and when they do you need to test that position instead of exiting.

[MG]

Do you mean change while right_Ind > left_Ind to while right_Ind >= left_Ind? Sorry if this is a stupid question, there is nothing about that in the description of the algorithm in my assignment.

The weird thing is, my code is correct, because when I call searchForIt(L,2), and L = [1 3 5 9 2 4 0 8], matlab sorts L and it becomes B, then it finds the entry '2' in the sorted list and spits out '3', or the position of '2' in the sorted list. However, my prof wants me to find the position of '2' in the original, scrambled list. So how do I do that? I'm confused. What was the purpose of sorting the list if I have to scramble it again.

[Walter Roberson]

You can still use "while right_Ind > left_Ind" but if you do then afterwards you need to check in case the two are equal and that the number is found there. But it is easier to just use >= instead of > to cover the situation.

I have no idea what your assignment said. The usual way to handle the situation is to not use a binary search on an unsorted matrix. You might wonder what is wrong with doing the sort followed by a binary search, and the answer to that is that sorting is slower than a linear search for a single target value, as that involves at most length(L) comparisons but the best sort algorithms in the world are never less than length(L)*log(length(L)) for some arrangements of L.

If you are going to use sort() then read the documentation for it more carefully and see what other information you can ask it to return.

Answer 2

[Image Analyst]

Try it this way:

index = find(L == 2, 1, 'first');