制作二分查找函数

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) {&nbsp; &nbsp; if (array.length <= 1) {&nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; }&nbsp; &nbsp; // Start with an initially sorted part.&nbsp; &nbsp; int loSorted = array.length - 1;&nbsp; &nbsp; //int hiSorted = array.length;&nbsp; &nbsp; while (loSorted > 0) {&nbsp; &nbsp; &nbsp; &nbsp; // Take one from the array&nbsp; &nbsp; &nbsp; &nbsp; int x = array[0];&nbsp; &nbsp; &nbsp; &nbsp; // Where in the sorted part to insert?&nbsp; &nbsp; &nbsp; &nbsp; int insertI = insertPosition(array, loSorted);&nbsp; &nbsp; &nbsp; &nbsp; // Insert x at insertI&nbsp; &nbsp; &nbsp; &nbsp; ...&nbsp; &nbsp; &nbsp; &nbsp; --loSorted;&nbsp; &nbsp; }}

Answer 2

谢谢您的意见。我稍微改变了功能，现在似乎可以工作了` public static void insertSort(int[] array, int lo, int hi){ int mid; 整数位置；&nbsp; &nbsp; for (int i = 1; i < array.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; int j = i -1;&nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; int x = array[i];&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; while (lo <= hi) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mid = lo + (hi -lo)/2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (x == array[mid]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pos = mid;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (x > array[mid]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lo = mid+1;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (x < array[mid]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hi = mid-1;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; while (j >= 0 && array[j] > x) {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[j + 1] = array[j];&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j = j - 1;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; array[j + 1] = x;&nbsp;&nbsp;&nbsp; &nbsp; }}问题似乎出在最后一部分，我试图将元素移动到正确的位置。该功能可能并不完美，因此欢迎建设性批评:)

Answer 3

每当我需要二分搜索时，我的函数看起来如下：public static void binarySearch(int arr[], int first, int last, int key){&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;int mid = (first + last)/2;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;while( first <= last ){&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ( arr[mid] < key ){&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; first = mid + 1;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else if ( arr[mid] == key ){&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Element is found at index: " + mid);&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;last = mid - 1;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mid = (first + last)/2;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if ( first > last ){&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Element is not found!");&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp;&nbsp;在您的 main 方法中，调用如下所示：public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;int arr[] = {10,20,30,40,50};&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int key = 30;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int last=arr.length-1;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; binarySearch(arr,0,last,key);&nbsp; &nbsp; &nbsp;&nbsp; &nbsp; }我希望我能够帮助你！