java数组操作2.折半查找

约定不等于承诺〃 2022-05-23 08:20 175阅读 0赞

//对数组的操作

//折半查找  
class ExampleDemo1  
\{  
 //主函数  
 public static void main(String\[\] args)  
 \{  
  int arr\[\]=\{5,1,6,4,2,8,9\};  
  int Index=GetIndex(arr,2);  
  System.out.println("Index "+Index);  
    
 \}  
 public static int GetIndex(int \[\] arr,int key)  
 \{  
  for (int i=0;i<arr.length;i++)  
  \{  
   if (arr\[i\]==key)  
  return i;  
  \}  
   return -1;//如果返回值为-1那么说明在数组中不含有该元素  
 \}

\}定位函数  
//对数组的操作  
//折半查找  
注意：该算法操作的数组必须有序  
class ExampleDemo2  
\{  
 public static void main(String\[\] args)  
 \{  
  int arr\[\]=\{0,1,2,3,4,5,6,7,8,9\};//有序表  
  //折半查找调用  
  int key=Search(arr,8);  
  System.out.println("Key:"+key);  
 \}  
 public static int Search(int \[\]arr,int key)  
 \{  
  int min=0;  
  int max=arr.length-1;  
  int mid=(min+max)/2;  
  while(arr\[mid\]!=key)  
  \{if (arr\[key\]>mid)  
  min=mid+1;  
  else if (arr\[key\]<mid)  
  max=max-1;  
  if(min>max)  
  mid=(min+max)/2;  
  \}  
  return mid;  
 \}  
\}  
//改正后的程序 代码如下：  
class Example1\_1  
\{  
 public static void main(String\[\] args)  
 \{  
  int arr\[\]=\{1,2,3,4,5,6,7,8,9\};//有序表  
  //折半查找调用  
  int key=Search(arr,8);  
  System.out.println("Key:"+key);  
 \}  
 public static int Search(int \[\]arr,int key)  
 \{  
  int min=0;//初始化Min  
  int max=arr.length-1;//初始化max  
  int mid=(min+max)/2;//取半取整  
  while(arr\[mid\]!=key)//判断语句 当未查找到时：  
  \{if (key>arr\[mid\])//注意：如果大于的话，我们向后找  
  min=mid+1;  
  else if (key<arr\[mid\]) //反之，向前  
  max=max-1;  
  //if(min>max)//判空   
  mid=(min+max)/2;  
  \}  
  return mid;  
 \}  
\}//折半查找//经验：用Editplus编译过的程序无法运行，报错为找不到或无法加载主类可能是因为主类的名字不同，或者在之前我们运行过其他的程序  
//折半查找的第二种方法  
class Example1\_1  
\{  
 public static void main(String\[\] args)  
 \{  
  int arr\[\]=\{1,2,3,4,5,6,7,8,9\};//有序表  
  //折半查找调用  
  int key=Search(arr,8);  
  System.out.println("Key:"+key);  
 \}  
 public static int Search(int \[\]arr,int key)  
 \{  
  int min=0;  
  int max=arr.length-1;  
  int mid;  
  while(min<=max)  
  \{  
   mid=(min+max)/2;  
   if (key>arr\[mid\])  
  min=mid+1;  
  else if (key<arr\[mid\])  
  max=max-1;  
  else  
   return mid;  
  \}  
  return -1;  
 \}  
\}  
//对数组的操作