Двоичный поиск

[mikebrownen]

Я пыталс сделть двоичный поиск который как параметры принимает только указатель на начало массива, количество элементов и искомый элемент. Программа работает только если элемент всегда будетт находится справа, в ином случае у меня пишет сегментейшн фол. Помогите пожалуйста исправить. Спасибо!

#include <stdio.h>
#include <stdlib.h>
int l,r,m;

int indexinmas(int *left, int elem, int kol)
{
    int i;
    for(i=0;i<kol;i++)
        if (elem==left[i])
        return i;
}

int search(int *left, int k, int nel)
{


    if(l>r)
    {
        return -1;
    }
    else
    {
        m=l+(r-l)/2;
        if (k==left[m])
        {
            return m;
        }
        else
        {
            if (k<left[m])
            {
                search(left,k,m-1-l);
            }
            else
            {
                search(left+sizeof(int)*(m+1),k,r-m-1);
            }
        }
    }
}
int main()
{
    int nel;
    scanf("%d",&nel);
    int mas[nel];
    int i;
    for(i=0;i<nel;i++)
        scanf("%d",&mas[i]);
    printf("Chto nayti?");
    int find;
    scanf("%d",&find);
    l=0;
    r=nel-1;
    printf("%d",search(mas, find,nel-1));
    return 0;
}

[mikebrownen]

Можно ли как-нибудь обойтись без глобальных переменных?

[k1moshka]

int search(int *arrayPtr, int key, int low, int high) // в arrayPtr указатель на начало массива, key нужное значение, low нижняя граница "отрезка", high соответственно верхняя
{
int middle = (low + high) / 2;
if (key == arrayPtr[middle]) return middle + 1;
    else
        if (key > arrayPtr[middle]) { low = middle; search(arrayPtr, key, low, high); }
            else
            { high = middle; search(arrayPtr, key, low, high); }

}

и надо сказать, что двоичный поиск используется только в упорядоченном массиве.
А зачем тебе глобальные переменные?

[An1ka]

Сообщение от mikebrownen

Можно ли как-нибудь обойтись без глобальных переменных?

Переменные можно объявить локально (например, в main), а потом передавать их в функции в качестве параметров.

[mikebrownen]

Нельзя передавать границы массива. можно передавать только указатель на начало массива и количество элеметов и искомый элемент. Все!

[k1moshka]

оке немного переделал

int search(int *arrayPtr, int key, int count)
{
int static iter = 1;
int static low;
int static high;

if (iter == 1) { low = 0; high = count; }
iter++;
int middle = (low + high) / 2;

if (key == arrayPtr[middle]) return middle + 1;
    else
        if (key > arrayPtr[middle]) { count /= 2; low = middle; search(arrayPtr, key, count); }
            else
            { high = middle; count /= 2; search(arrayPtr, key, count); }

}

[Сыроежка]

Сообщение от k1moshka

оке немного переделал

int search(int *arrayPtr, int key, int count)
{
int static iter = 1;
int static low;
int static high;

if (iter == 1) { low = 0; high = count; }
iter++;
int middle = (low + high) / 2;

if (key == arrayPtr[middle]) return middle + 1;
    else
        if (key > arrayPtr[middle]) { count /= 2; low = middle; search(arrayPtr, key, count); }
            else
            { high = middle; count /= 2; search(arrayPtr, key, count); }

}

Совершенно не понятно,зачем такие причуды со статическими переменными в коде? Как связан вызов вашей функции дляодного массива с вызововм этой жефункции для другого массива?! То есть зачем передавать из одного вызова в другой статические данные?!

[mikebrownen]

Можно ли как то сделать чтобы выводилось если ничего не нашлось минус один? когда я вставляю такую строчку во внутреннуюю проверку условия он ищет только в нижней половине массива if (middle=1) return -1;

[mikebrownen]

я пробовал задеййствовать счетчик итераций но все равно ничего не получается...