制作二分查找函数

Question

我正在做一项家庭作业任务，我应该创建一个执行二进制插入排序的函数，但我的函数似乎无法正常工作。这里我尝试将二分查找函数与插入排序函数结合起来（作业任务中指定需要采用函数的形式：insertionSort(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 并且如果 lo > hi）2 5 3 8 5（如果 lo==hi）不过，我期待的是一个排序列表...知道我做错了什么吗？

Answer 1

只是为了给你一个可能的想法：

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;

    }

}

Answer 2

谢谢您的意见。我稍微改变了功能，现在似乎可以工作了

` public static void insertSort(int[] array, int lo, int hi){ int mid; 整数位置；

    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;  

    }

}

问题似乎出在最后一部分，我试图将元素移动到正确的位置。该功能可能并不完美，因此欢迎建设性批评:)

Answer 3

每当我需要二分搜索时，我的函数看起来如下：

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!");  

           }  

         }  

在您的 main 方法中，调用如下所示：

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);     

    }

我希望我能够帮助你！