制作二分查找函数
Making a binary search function
我正在做一个家庭作业,我应该创建一个函数来执行二进制插入排序,但我的函数似乎无法正常工作。
这里我尝试过将二分查找函数和插入排序函数结合起来(在作业中指定需要是函数形式:insertionSort(int[] array, int lo,诠释喜))
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)
不过我期待的是一个排序列表...
知道我做错了什么吗?
每当我需要二进制搜索时,我的函数看起来如下:
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);
}
希望对您有所帮助!
只是给你一个可能的想法:
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;
}
}
感谢您的意见。我稍微更改了功能,现在似乎可以使用了
` public static void insertionSort(int[] array, int lo, int hi){
中间;
国际职位;
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;
}
}
问题似乎出在最后一部分,我试图将元素移动到正确的位置。功能可能还不够完善,欢迎建设性的批评:)
我正在做一个家庭作业,我应该创建一个函数来执行二进制插入排序,但我的函数似乎无法正常工作。
这里我尝试过将二分查找函数和插入排序函数结合起来(在作业中指定需要是函数形式:insertionSort(int[] array, int lo,诠释喜))
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)
不过我期待的是一个排序列表... 知道我做错了什么吗?
每当我需要二进制搜索时,我的函数看起来如下:
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);
}
希望对您有所帮助!
只是给你一个可能的想法:
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;
}
}
感谢您的意见。我稍微更改了功能,现在似乎可以使用了
` public static void insertionSort(int[] array, int lo, int hi){ 中间; 国际职位;
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;
}
}
问题似乎出在最后一部分,我试图将元素移动到正确的位置。功能可能还不够完善,欢迎建设性的批评:)