多平台统一管理软件接口，如何实现多平台统一管理软件接口
260
2023-01-19
java实现二分法的完整代码
java实现二分法的完整代码
二分法查找，顾名思义就是要将数据每次都分成两份然后再去找到你想要的数据，我们可以这样去想，二分法查找很类似与我们平时玩的猜价格游戏，当你报出一个价格时裁判会告诉你价格相对于真实值的高低，倘若是低了那我们一定会再说出一个略高的价格，反之亦然。在二分法查找时要求传入的数据必须已经有序，假设现在为升序，然后每次将所寻找的值与中间值(数组左边界+(右边界-左边界)/2)作比较，大了则去寻找中间值左侧数据，小则寻找中间值右侧数据。
二分法查找比较局限性的就是只能操作一个已经排序了的数组。
方法一
下面为一个二分法实现的完整代码
package dichotomy;
import java.util.Arrays;
import java.util.Scanner;
import static java.lang.System.out;
public class Erchange {
private static Scanner in;
public int find(int a[],int b) //a为所要查找的数
{
int mid,low=0,high;
high=a.length-1;
while(low<=high)
{
mid=low+(high-low)/2;
{
high=mid-1;
}
else if(b>a[mid])
{
low=mid+1;
}
else
{
return mid+1;
}
}
return 0;
}
public static void main(String[] args) {
int a[];
int t;
int sum=0;
Erchange p=new Erchange();
int q2 = 0;
in = new Scanner(System.in);
out.println("请输入数组长度");
q2= in.nextInt();
a=new int [q2];
out.println("请输入数组元素");
for(int i=0;i { a[i]=in.nextInt(); } out.println("排序后数组为"); Arrays.sort(a); for (int i = 0; i < a.length; i++) { out.print(a[i]+" "); } out.println(); out.println("请输入所要查找的数若未查找到该数则输出-1"); q2=in.nextInt(); for(int i=0;i { if(q2==a[i]) { t=1; } else { t=0; } sum=sum+t; } if(sum==0) { out.println("-1"); } else { out.println("所输入的数在第"+p.find(a,q2)+"位"); } } 方法二 代码实现： public class BinarySearch { //进行二分法查找的前提是数组已经有序！ public static int rank(int key,int nums[]) { //查找范围的上下界 int low=0; int high=nums.length-1; //未查找到的返回值 int notFind=-1; while(low<=high) { //二分中点=数组左边界+(右边界-左边界)/2 //整数类型默认取下整 int mid=low+(high-low)/2; //中间值是如果大于key if(nums[mid]>key) { //证明key在[low,mid-1]这个区间 //因为num[mid]已经判断过了所以下界要减一 high=mid-1; }else if(nums[mid] { //证明key在[mid+1,high]这个区间 //同样判断过mid对应的值要从mid+1往后判断 low=mid+1; } else { //查找成功 return mid; } } //未成功 return notFind; } public static void main(String[] args) { System.out.println("请输入数据数量："); Scanner scanner=new Scanner(System.in); int amount=scanner.nextInt(); int num; int nums[]=new int[amount]; int i=0; while(i { nums[i]=scanner.nextInt(); i++; } Arrays.sort(nums); System.out.println("请输入想要查找的值"); int key=scanner.nextInt(); int answer=rank(key,nums); if(answer!=-1) { System.out.println("所查找的数据存在："+nums[answer]); } else { System.out.println("您所查找的数据不存在"); } } } 方法三、算法代码实现之二分法查找 封装成类： package com.roc.algorithms.search; /** * 二分法查找 * * @author roc */ public class BinarySearch { /** * @param a 升序排列的数组 * @param k 待查找的整数 * @return 如果查到有就返回对应角标，没有就返回-1 */ public static int search(int[] a, int k) sldEEDg{ int lo = 0, hi = a.length - 1; while (lo <= hi) { int m = (lo + hi) >> 1; if (a[m] < k) { lo = m + 1; } else if (a[m] > k) { hi = m - 1; } else { return m; } } return -1; } } 测试： int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; System.out.println(BinarySearch.search(a, 6)); 输出： 6
{
a[i]=in.nextInt();
}
out.println("排序后数组为");
Arrays.sort(a);
for (int i = 0; i < a.length; i++) {
out.print(a[i]+" ");
}
out.println();
out.println("请输入所要查找的数若未查找到该数则输出-1");
q2=in.nextInt();
for(int i=0;i { if(q2==a[i]) { t=1; } else { t=0; } sum=sum+t; } if(sum==0) { out.println("-1"); } else { out.println("所输入的数在第"+p.find(a,q2)+"位"); } } 方法二 代码实现： public class BinarySearch { //进行二分法查找的前提是数组已经有序！ public static int rank(int key,int nums[]) { //查找范围的上下界 int low=0; int high=nums.length-1; //未查找到的返回值 int notFind=-1; while(low<=high) { //二分中点=数组左边界+(右边界-左边界)/2 //整数类型默认取下整 int mid=low+(high-low)/2; //中间值是如果大于key if(nums[mid]>key) { //证明key在[low,mid-1]这个区间 //因为num[mid]已经判断过了所以下界要减一 high=mid-1; }else if(nums[mid] { //证明key在[mid+1,high]这个区间 //同样判断过mid对应的值要从mid+1往后判断 low=mid+1; } else { //查找成功 return mid; } } //未成功 return notFind; } public static void main(String[] args) { System.out.println("请输入数据数量："); Scanner scanner=new Scanner(System.in); int amount=scanner.nextInt(); int num; int nums[]=new int[amount]; int i=0; while(i { nums[i]=scanner.nextInt(); i++; } Arrays.sort(nums); System.out.println("请输入想要查找的值"); int key=scanner.nextInt(); int answer=rank(key,nums); if(answer!=-1) { System.out.println("所查找的数据存在："+nums[answer]); } else { System.out.println("您所查找的数据不存在"); } } } 方法三、算法代码实现之二分法查找 封装成类： package com.roc.algorithms.search; /** * 二分法查找 * * @author roc */ public class BinarySearch { /** * @param a 升序排列的数组 * @param k 待查找的整数 * @return 如果查到有就返回对应角标，没有就返回-1 */ public static int search(int[] a, int k) sldEEDg{ int lo = 0, hi = a.length - 1; while (lo <= hi) { int m = (lo + hi) >> 1; if (a[m] < k) { lo = m + 1; } else if (a[m] > k) { hi = m - 1; } else { return m; } } return -1; } } 测试： int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; System.out.println(BinarySearch.search(a, 6)); 输出： 6
{
if(q2==a[i])
{
t=1;
}
else
{
t=0;
}
sum=sum+t;
}
if(sum==0)
{
out.println("-1");
}
else
{
out.println("所输入的数在第"+p.find(a,q2)+"位");
}
}
方法二
代码实现：
public class BinarySearch {
//进行二分法查找的前提是数组已经有序！
public static int rank(int key,int nums[])
{
//查找范围的上下界
int low=0;
int high=nums.length-1;
//未查找到的返回值
int notFind=-1;
while(low<=high)
{
//二分中点=数组左边界+(右边界-左边界)/2
//整数类型默认取下整
int mid=low+(high-low)/2;
//中间值是如果大于key
if(nums[mid]>key)
{
//证明key在[low,mid-1]这个区间
//因为num[mid]已经判断过了所以下界要减一
high=mid-1;
}else if(nums[mid] { //证明key在[mid+1,high]这个区间 //同样判断过mid对应的值要从mid+1往后判断 low=mid+1; } else { //查找成功 return mid; } } //未成功 return notFind; } public static void main(String[] args) { System.out.println("请输入数据数量："); Scanner scanner=new Scanner(System.in); int amount=scanner.nextInt(); int num; int nums[]=new int[amount]; int i=0; while(i { nums[i]=scanner.nextInt(); i++; } Arrays.sort(nums); System.out.println("请输入想要查找的值"); int key=scanner.nextInt(); int answer=rank(key,nums); if(answer!=-1) { System.out.println("所查找的数据存在："+nums[answer]); } else { System.out.println("您所查找的数据不存在"); } } } 方法三、算法代码实现之二分法查找 封装成类： package com.roc.algorithms.search; /** * 二分法查找 * * @author roc */ public class BinarySearch { /** * @param a 升序排列的数组 * @param k 待查找的整数 * @return 如果查到有就返回对应角标，没有就返回-1 */ public static int search(int[] a, int k) sldEEDg{ int lo = 0, hi = a.length - 1; while (lo <= hi) { int m = (lo + hi) >> 1; if (a[m] < k) { lo = m + 1; } else if (a[m] > k) { hi = m - 1; } else { return m; } } return -1; } } 测试： int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; System.out.println(BinarySearch.search(a, 6)); 输出： 6
{
//证明key在[mid+1,high]这个区间
//同样判断过mid对应的值要从mid+1往后判断
low=mid+1;
}
else
{
//查找成功
return mid;
}
}
//未成功
return notFind;
}
public static void main(String[] args) {
System.out.println("请输入数据数量：");
Scanner scanner=new Scanner(System.in);
int amount=scanner.nextInt();
int num;
int nums[]=new int[amount];
int i=0;
while(i { nums[i]=scanner.nextInt(); i++; } Arrays.sort(nums); System.out.println("请输入想要查找的值"); int key=scanner.nextInt(); int answer=rank(key,nums); if(answer!=-1) { System.out.println("所查找的数据存在："+nums[answer]); } else { System.out.println("您所查找的数据不存在"); } } } 方法三、算法代码实现之二分法查找 封装成类： package com.roc.algorithms.search; /** * 二分法查找 * * @author roc */ public class BinarySearch { /** * @param a 升序排列的数组 * @param k 待查找的整数 * @return 如果查到有就返回对应角标，没有就返回-1 */ public static int search(int[] a, int k) sldEEDg{ int lo = 0, hi = a.length - 1; while (lo <= hi) { int m = (lo + hi) >> 1; if (a[m] < k) { lo = m + 1; } else if (a[m] > k) { hi = m - 1; } else { return m; } } return -1; } } 测试： int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; System.out.println(BinarySearch.search(a, 6)); 输出： 6
{
nums[i]=scanner.nextInt();
i++;
}
Arrays.sort(nums);
System.out.println("请输入想要查找的值");
int key=scanner.nextInt();
int answer=rank(key,nums);
if(answer!=-1)
{
System.out.println("所查找的数据存在："+nums[answer]);
}
else
{
System.out.println("您所查找的数据不存在");
}
}
}
方法三、算法代码实现之二分法查找
封装成类：
package com.roc.algorithms.search;
/**
* 二分法查找
*
* @author roc
*/
public class BinarySearch {
/**
* @param a 升序排列的数组
* @param k 待查找的整数
* @return 如果查到有就返回对应角标，没有就返回-1
*/
public static int search(int[] a, int k) sldEEDg{
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int m = (lo + hi) >> 1;
if (a[m] < k) {
lo = m + 1;
} else if (a[m] > k) {
hi = m - 1;
} else {
return m;
}
}
return -1;
}
}
测试：
int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(BinarySearch.search(a, 6));
输出：
6
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
相关文章
发表评论
暂时没有评论，来抢沙发吧~