Бинарный поиск в С

Я хочу сделать бинарный поиск в сортированном массиве. Без рекурсии.

int BinarySearch(int arr[], int low, int high, int key)
{
     int mid; // = (low + high)/2;
     int  done = 0;
     
     if (high < low) 
           return -1;
       
     mid = (low + high)/2;
         
     while (!done)
     {
         if(key==arr[mid])
             return mid;
         else if (key > arr[mid])
             mid = ((mid+1) + high) / 2;
         else if (key < arr[mid])
            mid = (low + (mid-1)) / 2;
     }
     
     return -1;
}

Если искомый элемент (key) есть в массиве (arr) то все нормально, функция возвращает индекс массива. Но если элемента нет в массиве я кручусь все время в цикле (while (!done)).
Я что то никак не соображу по какому условию выйти из цикла.

Надо сжимать интервал, если он сжался, а ничего не нашлось, тогда ой. шпаргалка под спойлером, лучше не подглядывать, без крайней нужды. а додумать. потому что все несложно. Главное не забыть менять done - а то же там константа, поэтому цикл будет вращаться до конца света.

+

int BinarySearch(int arr[], int low, int high, int key) { int mid; // = (low + high)/2; int done = 0; if (high < low) return -1; while (1) { mid = (low + high)/2; if(key==arr[mid]) return mid; if (low==high) return -1; if (key > arr[mid]) low = (mid+1) else high = (mid-1); } } int BinarySearch_rec(int arr[], int low, int high, int key) { int mid; // = (low + high)/2; int done = 0; if (high < low) return -1; mid = (low + high)/2; if(key==arr[mid]) return mid; if (low==high) return -1; if (key > arr[mid]) low = (mid+1) ; else high = (mid-1); return BinarySearch_rec(arr, low, high, key); }

По условию done = y, где у != 0
например внутри цикла

Vladimir Baskakov
Надо сжимать интервал, если он сжался, а ничего не нашлось, тогда ой. шпаргалка под спойлером, лучше не подглядывать, без крайней нужды. а додумать. потому что все несложно. Главное не забыть менять done - а то же там константа, поэтому цикл будет вращаться до конца света.

большое спасибо. работает. но у меня тут еще одна проблема. я хочу вставлять элемент если он не найден. то есть я хочу вернуть не -1 а индекс на место которого я хочу вставить элемент. соответсвенно все элементы перед ним я сдвину вправо. как мне модифицировать функцию?
я думал ввести условие

 else if (key > arr[mid] && key <  arr[mid+1])

но что то в нем не так.

а проблема в том что это недостаточное условие. нужен какой то флаг - элемент не найден. но тогда получается нужно делать еще один пробег?

jenya7, пробег делать не надо, достаточно ещё одного сравнения. Вот из Вики:

 
   while (first < last) {
        size_t mid = first + (last - first) / 2;

        if (x <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }

    /* Если условный оператор if (n == 0) и т.д. в начале опущен -
     * значит, тут раскомментировать!
     */
    if (/* last < n && */ a[last] == x) {
        /* Искомый элемент найден. last - искомый индекс */
        return FOUND(last);
    } else {
        /* Искомый элемент не найден. Но если вам вдруг надо его
         * вставить со сдвигом, то его место - last.
         */
        return NOTFOUND(last);
    }

jenya7, а done чем не флаг? в integer разных значений как грязи весной ...

MBo

jenya7, пробег делать не надо, достаточно ещё одного сравнения. Вот из Вики: while (first < last) { size_t mid = first + (last - first) / 2; if (x <= a[mid]) last = mid; else first = mid + 1; } /* Если условный оператор if (n == 0) и т.д. в начале опущен - * значит, тут раскомментировать! */ if (/* last < n && */ a[last] == x) { /* Искомый элемент найден. last - искомый индекс */ return FOUND(last); } else { /* Искомый элемент не найден. Но если вам вдруг надо его * вставить со сдвигом, то его место - last. */ return NOTFOUND(last); }

а FOUND это что? дефайн?

а FOUND это что? дефайн?

Да, там возвращается структура из двух членов - индекс и boolean признак. Достаточно нелепо.
Варианты:
- изменить прототип, индекс сделать аргументом, а результат - boolean
- возвращать положительный индекс при наличии, отрицательный при отсутствии.
- при использовании исключительно для поиска места для вставки - оставить обычный интерфейс

а где изменяется n?