Создание бинарной функции поиска - PullRequest
Новая
       26

Создание бинарной функции поиска

0 голосов
/ 19 сентября 2019

Я работаю над заданием на домашнее задание, в котором я должен создать функцию, которая будет выполнять сортировку двоичных вставок, но моя функция, похоже, не работает должным образом.

Здесь я попытался объединить бинарную функцию поиска с функцией сортировки вставкой (в задаче домашней работы указывается, что она должна быть в форме функции: inserttionSort (int [] array, int lo, int hi)) 

 public static void insertionSort(int[] array, int lo, int hi){
        int mid; 
        int pos; 

        for (int i = 1; i < array.length; i++) {

            int x= array[i]; 

            while (lo < hi) {
                mid = lo + (hi -lo)/2;
                if (x == array[mid]) {
                    pos = mid; 
                }
                if (x > array[mid]) {
                    lo = mid+1; 
                }
                else if (x < array[mid]) {
                    hi = mid-1; 
                }
            }
            pos = lo; 

                for (int j = i; j > pos; j--) {
                array[j] = array[j-1]; 
            }
            array[pos] = x; 
        }
    }

Если я попытаюсь запустить его со списком {2,5,1,8,3}, вывод будет

2 5 1 3 1(если lo hi)

2 5 3 8 5 (если lo == hi)

Хотя я ожидаю, что это отсортированный список ... Любая идеячто я делаю не так?

Ответы [ 3 ]

0 голосов
/ 19 сентября 2019

Просто чтобы дать вам возможную идею: 

public static void insertionSort(int[] array) {
    if (array.length <= 1) {
        return;
    }

    // Start with an initially sorted part.
    int loSorted = array.length - 1;
    //int hiSorted = array.length;

    while (loSorted > 0) {

        // Take one from the array
        int x = array[0];

        // Where in the sorted part to insert?
        int insertI = insertPosition(array, loSorted);

        // Insert x at insertI
        ...
        --loSorted;
    }
}
0 голосов
/ 19 сентября 2019

Спасибо за ваш вклад.Я немного изменил функцию, и теперь она работает

`public static void inserttionSort (int [] array, int lo, int hi) {int mid;int pos;

    for (int i = 1; i < array.length; i++) {
        int j = i -1;   
        int x = array[i]; 

        while (lo <= hi) {
            mid = lo + (hi -lo)/2;

            if (x == array[mid]) {
                pos = mid; 
                break; 
            }
            if (x > array[mid]) {
                lo = mid+1; 
            }
            else if (x < array[mid]) {
                hi = mid-1; 
            }
        }

        while (j >= 0 && array[j] > x) { 
            array[j + 1] = array[j]; 
            j = j - 1; 
        } 
        array[j + 1] = x;  
    }
}

проблема, похоже, заключалась в последней части, где я пытался переместить элементы в правильное положение.Функция, вероятно, не идеальна, так что конструктивная критика приветствуется:)

0 голосов
/ 19 сентября 2019

всякий раз, когда мне нужен бинарный поиск, моя функция выглядит следующим образом: 

public static void binarySearch(int arr[], int first, int last, int key){  
           int mid = (first + last)/2;  
           while( first <= last ){  
              if ( arr[mid] < key ){  
                first = mid + 1;     
              }else if ( arr[mid] == key ){  
                System.out.println("Element is found at index: " + mid);  
                break;  
              }else{  
                 last = mid - 1;  
              }  
              mid = (first + last)/2;  
           }  
           if ( first > last ){  
              System.out.println("Element is not found!");  
           }  
         }

В вашем основном методе вызов выглядит так: 

public static void main(String[] args) {
           int arr[] = {10,20,30,40,50};  
            int key = 30;  
            int last=arr.length-1;  
            binarySearch(arr,0,last,key);     
    }

Я надеюсь, что смог помочьвы!

...