大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
二分法查找,顾名思义就是要将数据每次都分成两份然后再去找到你想要的数据,我们可以这样去想,二分法查找很类似与我们平时玩的猜价格游戏,当你报出一个价格时裁判会告诉你价格相对于真实值的高低,倘若是低了那我们一定会再说出一个略高的价格,反之亦然。在二分法查找时要求传入的数据必须已经有序,假设现在为升序,然后每次将所寻找的值与中间值(数组左边界+(右边界-左边界)/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; if(ba[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
方法二
代码实现:
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]
方法三、算法代码实现之二分法查找
封装成类:
package com.roc.algorithms.search; /** * 二分法查找 * * @author roc */ public class BinarySearch { /** * @param a 升序排列的数组 * @param k 待查找的整数 * @return 如果查到有就返回对应角标,没有就返回-1 */ public static int search(int[] a, int k) { 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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持创新互联。