Форум программистов, компьютерный форум CyberForum.ru

Элемент в массиве через двоичную систему поиска - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Рекурсивная функция http://www.cyberforum.ru/cpp-beginners/thread443877.html
Нужна программа,которая рекурсивно переводит числа из десятичной системы в двоичную.
C++ delete динамического массива символов Простой код вываливается с ошибкой??? #include <iostream.h> #include <string.h> int main() { char * str; str = new char; str = "1234567890"; http://www.cyberforum.ru/cpp-beginners/thread443861.html
C++ Что можно написать
Вот хотел спросить, может что то подскажите что, какую программку можно написать(консоль), полезную Добавлено через 36 минут Просто хотелось по практиковаться, а не знаю что можно написать
C++ Оператор switch
Зависит ли a) объектный код от порядка меток case и default в данном операторе? б) если ответ на первый вопрос положителен, то тогда можно ли говорить, что при том или ином порядке меток case и default оператор switch выполняется быстрее ччем при другом?
C++ Целое четырехзначное число заменить числом, получающимся при записи его цифр в обратном порядке http://www.cyberforum.ru/cpp-beginners/thread443800.html
подскажите как заменить число в обратном порядке в С?
C++ Некомпилится простой код! Привет! Сразу к делу. Вот код #include <cstdlib> #include <iostream> #include <string.h> using namespace std; int main(int argc, char *argv) { unsigned long fibo; подробнее

Показать сообщение отдельно
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
11.02.2012, 18:07     Элемент в массиве через двоичную систему поиска
Цитата Сообщение от Dani Посмотреть сообщение
Здесь binary search, точно. Т.к. иначе билеберда получается.
Если телепатические способности Dani не подвели и больше никаких уточнений не придвидится, то и так сойдёт:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
/* понадобится для сортировки */
int asccmp(const void * a, const void * b){
    return *(int*)a - *(int*)b;
}
 
/* заполнение массива случайными числами */
void rndfill(int * arr, size_t size){
    while ( size-- )
        *arr++ = rand() % 10;
}
 
/* вывод на экран */
void dump(const int * arr, size_t size){
    while ( size-- )
        printf("%d%c", *arr++, ( size ) ? ' ' : '\n');
}
 
/* возвращает указатель на последнее найденное значение или NULL, counter - счётчик */
int * binsearch(const int * arr, size_t size, const int val, int * counter){
    const int * middle = arr + size / 2; /* указатель на середину массива */
    *counter += 1; /* отметились :) */
 
    if ( middle > arr ){ /* если элементов больше одного */
        if ( *(arr + size - 1) == val ) /* последний элемент */
            return (int*)(arr + size - 1);
        if ( *middle == val ) /* средний */
            return (int*)middle;
        if ( *middle > val ) /* искомый элемент между первым и средним */
            return binsearch(arr, middle - arr, val, counter);
        return binsearch(middle, size - (middle - arr), val, counter); /* в другом случае */
    }
    if ( *arr == val ) /* если нашли в начале массива */
        return (int*)arr;
        
    /* не нашли */
    return NULL;
}
 
int main(void){
    int * arr, val, * found;
    size_t size, counter;
    
    srand(time(NULL)); /* это чтобы при каждом запуске программы циферки разные были */
    
    while ( printf("Number of elements: ") && scanf("%u", &size) == 1 && size && printf("Value to search: ") && scanf("%d", &val) == 1 ){
        /* создаём и заполняем массив */
        if ( ! ( arr = (int*)malloc(sizeof(int) * size) ) ){
            perror("malloc");
            exit(1);
        }
        
        rndfill(arr, size);
        qsort(arr, size, sizeof(int), asccmp);
        printf("Array:\n");
        dump(arr, size);
        
        /* ищем элемент */
        counter = 0;
        if ( found = binsearch(arr, size, val, &counter) )
            printf("Last value %d found at pos %u with %u attempt(s)\n", val, found - arr + 1, counter);
        else
            printf("Can't find value %d after %u attempt(s)\n", val, counter);
        
        /* удаляем массив */
        free(arr);
    }
    
    exit(0);
}
 
Текущее время: 03:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru