How to find position (array index ) of a number in a given array?

Question

0.00/5 (No votes)

See more:

I have to find the position (array index) of a number in an array, the number can lie in between any other two numbers in the array. I have written code for this but I want some alternative way to do this.

example: let the array be given as

float arr[]={1.5, 3.65, 4.9, 8.4, 10.6, 17.5, 19.45, 21.86, 25.67, 30.65}; 
Now I have to find the position of 12.6 in the given array, since 12.6 lies between 10.6 and 17.5 in the above array so, it should return array index as 4. Is there any other way to do this? I know it can be done by using binary search but I don't know how to implement it (since the number is not present in array)

The array is sorted (ascending order)

What I have tried:

C++

#include<stdio.h>
int main()
{
    int position;
    int i;
    float num=12.6; // position of this number has to be determined i.e. it lies between 10.6 
                    // and 17.5 in the array given below so it should give array index as 4 
    float arr[]={1.5, 3.65, 4.9, 8.4, 10.6, 17.5, 19.45, 21.86, 25.67, 30.65}; // any random array

    for(i=0;i<10;i++)
    {
        if(arr[i] > num)
        {
            position=i-1;
            break;
        }
    }
    printf("array index is %d",position); // this gives index as 4

    return 0;
}

Posted 16-May-20 5:48am

Member 14818745

Updated 16-May-20 10:28am

Patrice T

v2

Add a Solution

Comments

KarstenK 16-May-20 13:48pm

The important point is that your array is sorted. When this clear, THEN the binary search is the right way to solve the task!!!

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

k5054 · Answer 1 · 2020-05-16T06:35:00

In this case the array is small, so a linear search is not a bad solution, but I suspect you teacher would like you to implement a binary search

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m - 1
        else:
            return m
    return unsuccessful

That description comes from Binary search algorithm - Wikipedia[^] You'll note that this version either returns the position or unsuccessful, so you'll have to think about how you might modify this algorithm to give you the result you want.

John R. Shaw · Answer 2 · 2020-05-16T07:02:00

Let us see:

You could do a 'while' loop.

C++

i = 0;
while (i++ < 10)
{
    ...
}

- OR -

i = 0;
while (i < 10)
{
    ...
    ++i;
}

Or a 'do while' loop.

C++

i = 0;
do
{
    ....
} while (++i < 10);

- OR -

i = 0;
do
{
   ...
   ++i;
} while (i < 10);

Or the dreaded 'goto'.

C++

int i = 0;
nextloop:
if (arr[i++] < num)
{
   goto nextloop;
}

- OR -

int i = 0;
nextloop:
if (arr[i] < num)
{
    ++i;
    goto nextloop;
}

Or you could create recursive algorithm.

C++

That requires more thought and I am too tired to explain that at the moment.

Note:
Always prefer pre-increment (++i) to post-increment (i++). There are vary valid reasons for this. But don't believe me, research what the creators of the languages have to say on the subject. Or simply draw a flow charts of both post and pre-increment and you will understand why.

Patrice T · Answer 3 · 2020-05-16T10:29:00

Your code have a few problems: how do you handle case where num is bigger or equal to last value in array ?

Quote:
I know it can be done by using binary search but I don't know how to implement it (since the number is not present in array)

If you know that value exist

C++

if(arr[i] = num)

ends the search, but if never equal, you need to use another condition.
For binary search, you need 2 pointers (indexes) where you know that num is between pointers.
When distance between pointers is 1, you know the answer.

How to find position (array index ) of a number in a given array?

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0