Форум программистов, компьютерный форум, киберфорум
Java для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/26: Рейтинг темы: голосов - 26, средняя оценка - 5.00
5 / 5 / 0
Регистрация: 22.10.2013
Сообщений: 103
1

Поиск элемента в массиве

15.06.2014, 01:32. Просмотров 5268. Ответов 4
Метки нет (Все метки)

Здравствуйте, задача такова: Нужно найти элемент алгоритмом золотого сечения или по другому бинарным поиском... Часть ковырнул, но часть элементов проскакивает.... Метод должен вернуть индекс элемента
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 public static int findVal(int[]arr, int val){
        int len = arr.length;
        int middle = len / 2;
        while(arr[middle] != val) {
            if (arr[middle] == val)
                return middle;
            else if (arr[middle] < val) {
                middle = (middle + len) / 2;
                len /= 2;
                if (arr[middle] == val)
                    return middle;
            } else if (arr[middle] > val) {
                middle = (len - middle) / 2;
                len /= 2;
                if (arr[middle] == val)
                    return middle;
            }
        }
        return middle;
    }
Добавлено через 8 часов 10 минут
В чем ошибка?(
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.06.2014, 01:32
Ответы с готовыми решениями:

Поиск элемента в упорядоченном массиве
Поиск элемента в упорядоченном массиве

Реализуйте двоичный поиск элемента X в массиве A
Дан массив A размера N и значение X. Реализуйте двоичный поиск элемента X в массиве A,...

Поиск нужного элемента в отсортированном массиве
Здраствуйте. Решаю задачу 2 день, неполучается. Подумал сюда обратиться. В общем задача такая. Есть...

Поиск индекса минимального элемента в массиве
Такая проблема: надо написать программку которая ищет индекс минимального элемента массива. Препод...

4
ɐwʎ ɔ vǝmоɔ dиw ɐʚонɔ
441 / 440 / 100
Регистрация: 14.10.2012
Сообщений: 1,147
Записей в блоге: 9
15.06.2014, 20:30 2
http://java-algo.blogspot.com/... st_11.html
1
16 / 16 / 6
Регистрация: 19.05.2014
Сообщений: 67
16.06.2014, 16:07 3
Цитата Сообщение от OlegPL Посмотреть сообщение
В чем ошибка?(
Два момента,
1. Бинарный поиск очень эффективен, поскольку тратит в худшем случае log2 операции для нахождения нужного элемента, однако для того чтобы бинарный поиск работал корректно, массив должен быть отсортирован (от меньшего до большего элемента или наоборот).
2. Бегло пробежался по коду, заметил несколько некорректных моментов, например что будет если массив не содержит искомого элемента? бесконечный цикл?)
1
Эксперт Java
2304 / 2144 / 546
Регистрация: 28.12.2010
Сообщений: 8,434
16.06.2014, 20:32 4
Цитата Сообщение от leopold_87 Посмотреть сообщение
тратит в худшем случае log2 операции для нахождения нужного элемента
То есть его время работы независит от длинны массива и он всегда найдет нужное число за ~0.3 итерации? Дайте мне такой алгоритм скорее!!!!
0
16 / 16 / 6
Регистрация: 19.05.2014
Сообщений: 67
17.06.2014, 08:04 5
Опечатка, кол-во операции для бинарного поиска log2n

Цитата Сообщение от KEKCoGEN Посмотреть сообщение
Дайте мне такой алгоритм скорее!!!!
и рекурсивный и циклицный методы:

Java
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
public static void main(String[] args) throws IOException {
        
        int array[] = {1,12,13,14,15,17,20,30,40,50,100,200};
        System.out.println("Рекурсия:");
        int index = findValRec(array,0,array.length-1,17);
        if (index!=-1){
        System.out.println("index: "+index + " элемент по индексу: " + array[index]);
        }
        else System.out.println("Элемент не найден");
        System.out.println("\n Цикл:");
        index = findVal(array,17);
        if (index!=-1){
            System.out.println("index: "+index + " элемент по индексу: " + array[index]);
            }
            else System.out.println("Элемент не найден");
     }
    
// цикличный метод бинарного поиска по сортированному массиву от меньшего к большему
public static int findVal(int[]arr, int val){
    int last = arr.length-1;
    int first = 0;
    
    while(first <= last) {
        int middle = (first+last) / 2;// индекс среднего элем
        if (arr[middle] == val)
            return middle;
        else if (arr[middle] < val) {
           first = middle+1;
        } 
        else{
           last = middle-1;
        }
    }
    return -1;// не нашли элемент
}
// рекурсивный метод бинарного поиска по сортированному массиву от меньшего к большему
public static int findValRec(int[] sortedArr, int first, int last, int val) {
    
    if (first > last) {
    return -1; // не нашли элемент
    }
    int middle = (first + last) / 2;  // индекс среднего элем
    if (sortedArr[middle] == val) {
        return middle;// нашли элемент
    }
    else if (sortedArr[middle] < val) {
            return findValRec(sortedArr, middle+1, last , val); //искомое число больше среднего
        } 
    else{ 
            return findValRec(sortedArr, first, middle-1, val);//искомое число меньше среднего
        }  
   }
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.06.2014, 08:04

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Реализуйте двоичный поиск элемента X в массиве A, предварительно отсортировав массив методом пузырька
Дан массив A размера N и значение X. Реализуйте двоичный поиск элемента X в массиве A,...

Выполните поиск элемента в массиве. Для поиска элемента используйте рекурсивную функцию
Выполните поиск элемента в массиве. Для поиска элемента используйте рекурсивную функцию. В случае,...

Поиск заданного элемента в упорядоченном массиве (бинарный поиск)
Заполнить одномерный массив из n элементов согласно таблицы. Размерность массива задать в виде...

Поиск заданного элемента в упорядоченном массиве(бинарный поиск)
Заполнить одномерный массив из n элементов по формуле приведенной в картинке. Размерность массива...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.