使用 Java 进行排序和二分搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19492402/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-08-12 17:43:48 来源:igfitidea点击:
Sorting and Binary search using Java
提问by Scarl
I was asked to sort and search an array. The sorting the array was simple and my code worked but then whenever I try to call the binary search method it works for the first element in the array but gives me "-1" as a result
我被要求对数组进行排序和搜索。对数组进行排序很简单，我的代码可以工作，但是每当我尝试调用二进制搜索方法时，它都适用于数组中的第一个元素，但结果给了我“-1”
My full code is as follows:
我的完整代码如下：
public static void main(String[] args) {
int[] array = new int[5];
array[0] = 50;
array[1] = 40;
array[2] = 10;
array[3] = 20;
array[4] = 100;
sort(array, (array.length - 1));
for (int x = 0; x < array.length; x++) {
System.out.println(" " + array[x]);
}
System.out.println("");
System.out.println("Binary search (R): " + rBsearch(array, 0, (array.length), 20));
}
public static void sort(int[] a, int last) {
if (last > 0) {
int max = findMax(a, last);
swap(a, last, max);
sort(a, last - 1);
}
}
public static int rBsearch(int[] L, int low, int high, int k) {
int mid = (low + high) / 2;
if (low > high) {
return -1;
} else if (L[mid] == k) {
return mid;
} else if (L[mid] < k) {
return rBsearch(L, k, mid + 1, high);
} else {
return rBsearch(L, k, low, mid - 1);
}
}
public static int findMax(int[] arr, int last) {
int max = 0;
for (int i = 0; i <= last; i++) {
if (arr[i] > arr[max]) {
max = i;
}
}
return max;
}
public static void swap(int[] arr, int last, int max) {
int temp = arr[last];
arr[last] = arr[max];
arr[max] = temp;
}
采纳答案by Pratik Shelar
You goofed up the binary search intervals
你搞砸了二分搜索间隔
public static int rBsearch(int[] L, int low, int high, int k) {
int mid = (low + high) / 2;
if (low > high) {
return -1;
} else if (L[mid] == k) {
return L[mid];
} else if (L[mid] < k) {
return rBsearch(L, mid + 1, high, k);
} else {
return rBsearch(L, low, mid - 1, k);
}
}
回答by G.S
回答by shikjohari
You did a mistake in calling the rBsearch method in the following lines Instead of
您在以下几行中调用 rBsearch 方法时犯了一个错误而不是
else if (L[mid] < k) {
return rBsearch(L, k, mid + 1, high);
} else {
return rBsearch(L, k, low, mid - 1);
}
You should use
你应该使用
else if (L[mid] < k) {
return rBsearch(L, mid + 1, high,k); //the order of the parameters
} else {
return rBsearch(L, low, mid - 1,k);
}
回答by Adeel Asghar
- Take Array From User
- Sort Array using Build-in Function of Java...
then Search Element using Binary Search....
import java.lang.reflect.Array; import java.util.Arrays; import java.util.Scanner; class BinarySearch { public static void main(String args[]) { int array[]; Scanner input = new Scanner(System.in); System.out.println("Enter number of elements:"); int Size_Of_Array = input.nextInt(); array = new int[Size_Of_Array]; System.out.println("Enter " + Size_Of_Array + " integers"); for (int counter = 0; counter < Size_Of_Array; counter++) array[counter] = input.nextInt(); Arrays.sort(array); System.out.println("Sorting Array is :-"); for (int counter = 0; counter < Size_Of_Array; counter++) System.out.println(array[counter]); System.out.println("Enter the search value:"); int Searching_item = input.nextInt(); int First_Index=0; int Last_Index=Size_Of_Array-1; int Middle_Index=(First_Index+Last_Index)/2; while(First_Index <= Last_Index) { if(array[Middle_Index] < Searching_item) { First_Index=Middle_Index+1; } else if ( array[Middle_Index] == Searching_item ) { System.out.println(Searching_item + " found at location " + (Middle_Index + 1) + "."); break; } else { Last_Index = Middle_Index - 1; } Middle_Index = (First_Index + Last_Index)/2; if ( First_Index > Last_Index ) { System.out.println(Searching_item + " is not found.\n"); } } } }
- 从用户获取数组
- 使用 Java 的内置函数对数组进行排序...
然后使用二分搜索搜索元素....
import java.lang.reflect.Array; import java.util.Arrays; import java.util.Scanner; class BinarySearch { public static void main(String args[]) { int array[]; Scanner input = new Scanner(System.in); System.out.println("Enter number of elements:"); int Size_Of_Array = input.nextInt(); array = new int[Size_Of_Array]; System.out.println("Enter " + Size_Of_Array + " integers"); for (int counter = 0; counter < Size_Of_Array; counter++) array[counter] = input.nextInt(); Arrays.sort(array); System.out.println("Sorting Array is :-"); for (int counter = 0; counter < Size_Of_Array; counter++) System.out.println(array[counter]); System.out.println("Enter the search value:"); int Searching_item = input.nextInt(); int First_Index=0; int Last_Index=Size_Of_Array-1; int Middle_Index=(First_Index+Last_Index)/2; while(First_Index <= Last_Index) { if(array[Middle_Index] < Searching_item) { First_Index=Middle_Index+1; } else if ( array[Middle_Index] == Searching_item ) { System.out.println(Searching_item + " found at location " + (Middle_Index + 1) + "."); break; } else { Last_Index = Middle_Index - 1; } Middle_Index = (First_Index + Last_Index)/2; if ( First_Index > Last_Index ) { System.out.println(Searching_item + " is not found.\n"); } } } }
