时间戳

首页 > 解决方案 > 制作二分查找函数

java - 制作二分查找函数

问题描述

我正在做一个家庭作业，我应该制作一个可以进行二进制插入排序的函数，但我的函数似乎无法正常工作。

这里我尝试将二分查找函数与插入排序函数结合起来（在作业任务中指定它需要采用函数的形式：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）

不过，我所期待的是一个排序列表......知道我做错了什么吗？

标签： javasortingbinary-searchinsertion-sort

解决方案

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

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

我希望我能帮助你！

推荐阅读