我设计了个折半的程序，不能编译，请大家看看，帮忙解决

神之梦

本帖最后由水。。。海于 2013-6-28 22:43 编辑

/**
*折半查找训练
*author @ 倪成伟
*/
/*思路：1.折半查找的基础是数组有序
2.找出中间角标代表的元素在与给定值比较，
通过改变最大与最小角标改变中间值，进
而找出所给值。
*/
class HalfSearch
{
public static int halfSearch(int a,int[] arr)
{
int mid;
int min=0;
int max=arr.length-1;
for(int x=0;x<arr.length;x++)
{
mid=(min+max)/2;
if(arr[mid]>a)
{
max=mid;
}
else if(arr[mid]<a)
{
min=mid;
}
else if(arr[mid]==a)
{
return mid;
}
else if(min>max) <font color="#ff0000">//这个代码去掉esle ,加上esle就执行不到这句话了</font>
{
return -1;
}
}
}
public static void main(String[] args)
{
int a=6;
int[] arr={1,2,5,8,9,10,21,22,33};
System.out.println(halfSearch(a,arr));
}
}

复制代码

这个程序是我构思的，编译后结果如图，想问的第一，这个程序可不可以实现折半查找？第二，返回结果说我没有返回值，但是我程序里设计了返回值，为什么？

/**
*折半查找训练
*author @ 倪成伟
*/
/*思路：1.折半查找的基础是数组有序
2.找出中间角标代表的元素在与给定值比较，
通过改变最大与最小角标改变中间值，进
而找出所给值。
*/
class HalfSearch
{
public static int halfSearch(int a,int[] arr)
{
int min=0;
int max=arr.length-1;
int mid=(min+max)/2;
while(arr[mid]!=a)
{
if(arr[mid]>a)
{
max=mid-1;
}
else if(arr[mid]<a)
{
min=mid+1;
}
else if(min>max)
return -1;
mid=(min+max)/2;
}
return mid;
}
public static void main(String[] args)
{
int a=6;
int[] arr={1,2,5,8,9,10,21,22,33};
System.out.println(halfSearch(a,arr));
}
}

复制代码

这个是修改过的，但是，查找不存在的数还是不行。

王楚鑫 · 王楚鑫

本帖最后由王楚鑫于 2013-6-28 21:14 编辑

我改了下你的代码、可以完成功能了、、、你看看能不能帮到你吧

/**
*折半查找训练
*author @ 倪成伟
*/
/*思路：1.折半查找的基础是数组有序
2.找出中间角标代表的元素在与给定值比较，
通过改变最大与最小角标改变中间值，进
而找出所给值。
*/
class HalfSearch
{
public static int halfSearch(int a,int[] arr)
{
int mid;
int min=0;
int max=arr.length-1;
while(min<=max)//保证查找区间非空
{
mid=(min+max)/2;
if(arr[mid]==a)
{
return mid;//查找成功返回
}
else if(arr[mid]>a)
{
max=mid-1;//缩小查找区间
}
else
{
min=mid+1;//缩小查找区间
}
}
return (-1);//查找失败
}
public static void main(String[] args)
{
int a=6;
//int a=22;
int[] arr={1,2,5,8,9,10,21,22,33};
System.out.println(halfSearch(a,arr));
}
}

复制代码

水。。。海 · 水。。。海

王楚鑫发表于 2013-6-28 21:09
我改了下你的代码、可以完成功能了、、、你看看能不能帮到你吧

你改过就可以完成，我看了你的代码你就是该了while循环里的条件，不过我觉得我的条件也没错啊？为什么就没结果？

sunriselzz · sunriselzz

本帖最后由 sunriselzz 于 2013-6-28 22:29 编辑

这是我个人总结的折半查找的几个不同方式,包括折半查找的优化,
以及调用数组工具类Arrays的二分查找方法直接进行二分查找,
顺序查找,遍历等. 有不足的地方,欢迎分享指正,谢谢!

import java.util.Arrays;
public class ArraysSearch {
/**
* 数组常见操作:
查找: 顺序查找折半查找
* @param args
*/
public static void main(String[] args) {
//数组的定义及初始化
int[] arr = new int[]{0,11,23,34,42,55,63,78,88,90};
//增强for循环遍历数组
printArr1(arr);
System.out.println("\n 查找数组中的某个元素: ");
//顺序查找
int index1 = getIndex(arr,63);
findElement(index1);
//折半查找1
int index3 = binarySearch(arr,63);
findElement(index3);
//折半查找2
int index2 = halfSearch(arr,63);
findElement(index2);
//折半查找3
int index4 = Arrays.binarySearch(arr, 77);
//如果元素不存在,返回这个元素负的插入位置再-1
findElement(index4);
}
//折半查找1
public static int binarySearch(int[] arr, int key) {
int min,max,mid;
min = 0;
max = arr.length-1;
mid = (min+max)/2;
while(key != arr[mid]){
if(key < arr[mid]){
max = mid - 1;
}else{
min = mid + 1;
}
if(max < min){
return -1;
}
mid = (min+max)/2;
}
return mid;
}
//打印所要查找元素的结果
public static void findElement(int index){
if(-1 != index){
System.out.println(" 所要查找元素在数组中的下标为: "+index);
}else{
System.out.println(" 数组中不存在该元素! ");
}
}
//对排序后的元素进行折半查找的优化2
public static int halfSearch(int[] arr,int key) {
int low = 0;
int high = arr.length-1;
int mid;
while(low <= high){
mid = (low+high)>>1;
if(key > arr[mid]){
low = mid + 1;
}else if(key < arr[mid]){
high = mid - 1;
}else{
return mid;
}
}
return -1; //若返回min,则可以获得往这个有序的数组中新存入一个元素,
//并依然保持这个数组有序的下标
}
//查找数组中的元素
public static int getIndex(int[] arr, int key) {
for (int i = 0; i < arr.length; i++) {
if(key == arr[i]){
return i;
}
}
return -1;
}
//普通for循环遍历数组arr
public static void printArr2(int[] arr) {
System.out.print(" 普通for循环遍历数组: { ");
for (int i = 0; i < arr.length; i++) {
if(i != arr.length-1){
System.out.print(arr[i]+",");
}else{
System.out.println(arr[i]+" }");
}
}
}
//增强for循环遍历数组arr
public static void printArr1(int[] arr) {
System.out.print(" 增强for循环遍历数组: { ");
for(int x : arr){
System.out.print(x+" ");
}
System.out.println("}");
}
}

复制代码

水。。。海 · 水。。。海

王楚鑫发表于 2013-6-28 21:09
我改了下你的代码、可以完成功能了、、、你看看能不能帮到你吧

我找到原因了，我写在代码上了，你可以看下

水。。。海 · 水。。。海

sunriselzz 发表于 2013-6-28 22:28
这是我个人总结的折半查找的几个不同方式,包括折半查找的优化,
以及调用数组工具类Arrays的二分查找方法直 ...

这个我可以好好研究了

张海龙 · 张海龙

这是我刚才做的。也运行出来了，你试试吧
public class Test10{
public static int halfSearch(int key,int[] arry){
int min=0;
int max=arry.length-1;
int mid=(min+max)/2;

for(int i=0;i<arry.length-1;i++){
if(key<arry[mid]){
max=mid;
mid=(min+max)/2;
}
else if(key>arry[mid]){
min=mid;
mid=(min+max)/2;
}
}
      if(key==arry[mid]){
return mid;
}
      else if(key==arry[mid+1]){
        return mid+1;
      }
      else return -1;
}
public static void main(String[] args) {
int[] arr={1,2,5,8,9,10,21,22,33};
int index=halfSearch(22,arr);
System.out.println(index);
      }
}

水。。。海 · 水。。。海

张海龙发表于 2013-6-28 22:39
这是我刚才做的。也运行出来了，你试试吧
public class Test10{
public static int halfSearch(int key,in ...

你这个写的复杂了，我优化了下你可以看下

/**
*折半查找训练
*author @ 倪成伟
*/
/*思路：1.折半查找的基础是数组有序
2.找出中间角标代表的元素在与给定值比较，
通过改变最大与最小角标改变中间值，进
而找出所给值。
*/
class HalfSearch
{
public static int halfSearch(int a,int[] arr)
{
int min=0;
int max=arr.length-1;
int mid=(min+max)/2;
while(arr[mid]!=a)
{
if(arr[mid]>a)
{
max=mid-1;
}
else if(arr[mid]<a)
{
min=mid+1;
}
if(min>max)
return -1;
mid=(min+max)/2;
}
return mid;
}
public static void main(String[] args)
{
int a=6;
int[] arr={1,2,5,8,9,10,21,22,33};
System.out.println(halfSearch(a,arr));
}
}

复制代码

张海龙 · 张海龙

我是为了用你的那个for循环，写的复杂了点，其实把min=mid;改为min=mid+1;  max=mid；改为max=mid-1;这样最后的 else if(key==arry[mid+1]){
                  return mid+1;
         }
就可以删除了。就简单了

水。。。海 · 水。。。海

张海龙发表于 2013-6-28 23:06
我是为了用你的那个for循环，写的复杂了点，其实把min=mid;改为min=mid+1; max=mid；改为max=mid-1;这样最 ...

有道理，有想法:lol

Just_Only · Just_Only

支持了。。。

帐号		自动登录	找回密码
密码			加入黑马

我设计了个折半的程序，不能编译，请大家看看，帮忙解决

评分

10 个回复

评分

评分

评分