Member 14818745 Ответов: 3

Как найти позицию (индекс массива ) числа в данном массиве?

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)


Что я уже пробовал:

#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;
}

KarstenK

Важным моментом является то, что Ваш массив отсортирован. Когда это ясно, то бинарный поиск-это правильный способ решения задачи!!!

3 Ответов

Рейтинг:
2

John R. Shaw

Давайте посмотрим:

Вы можете сделать цикл "пока".

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

- OR -

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


Или цикл "do while".

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

- OR -

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


Или ужасное "Гото".

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

- OR -

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


Или вы можете создать рекурсивный алгоритм.
That requires more thought and I am too tired to explain that at the moment.


Примечание:
Всегда предпочитайте пре-инкремент (++i) пост-инкременту (i++). Для этого есть несколько веских причин. Но не верьте мне, исследуйте, что говорят по этому поводу создатели языков. Или просто нарисуйте блок-схемы как пост -, так и пре-инкремента, и вы поймете, почему.

Рейтинг:
2

Patrice T

В вашем коде есть несколько проблем: как вы обрабатываете случай, когда num больше или равно последнему значению в массиве ?

Цитата:
Я знаю, что это можно сделать с помощью двоичного поиска, но я не знаю, как его реализовать (так как число отсутствует в массиве)

Если вы знаете, что ценность существует
if(arr[i] = num)

заканчивается поиск, но если он никогда не равен, вам нужно использовать другое условие.
Для двоичного поиска вам нужно 2 указателя (индекса), где вы знаете, что num находится между указателями.
Когда расстояние между указателями равно 1, Вы знаете ответ.

Рейтинг:
0

k5054

В этом случае массив невелик, поэтому линейный поиск-неплохое решение, но я подозреваю, что ваш учитель хотел бы, чтобы вы реализовали двоичный поиск

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

Это описание происходит от Алгоритм бинарного поиска - Википедия[^] Вы заметите, что эта версия либо возвращает позицию, либо неудачна, поэтому вам придется подумать о том, как вы могли бы изменить этот алгоритм, чтобы дать вам желаемый результат.