本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

暂无数据

二分查找

发布于2021-03-13 13:40     阅读(1083)     评论(0)     点赞(23)     收藏(2)


二分查找

二分查找是一种快速查找数据的算法,也叫折半查找,每次查询后数据的返回都会缩小一半,加快搜索的速度。二分查找的前提是数据必须是有序的,否则无法查找。

主要构思

  • 定义一个最大下标,最小下标,和中间下标;
  • 用while循环去循环,while 的条件为:中间下标所对应的数不等于当前查找的数;(如果不满足就返回当前定义的初始化的下标);
  • while里加入if条件判断:最大下标要大于等于最小下标;避免查询不到元素;
  • 当while循环时,如果当前的数小于当前中间下标对应的数时,下一次循环的数组最大下标就等于max=mid-1 , 例如( 1 - 100 中查找10;10 小于 50,所以数组下次的最大下标就是 50 - 1 了,下次循环的最小下标是 0,最大下标是 49,达到每次都对折一半查找范围); 如果当前的数大于中间下标所对应的数时,下一次循环的数组最小下标就是 min = mid + 1 , 例如(1-100 中查找60;10 大于 50;所以数组下次开始的最小下标是 50 + 1;最大下标还是 数组长度-1);
  • 每次实现对半查找都会得到一个新的中间下标;直到循环得到的中间下标对应的数等于所查找的数;

示例代码

package com.etime6;

import java.util.Arrays;

public class Test01 {

	public static void main(String[] args) {
		/**
		 * //二分查找
		 * 二分查找是一种快速检索数据的算法。折半查找。
		 * 每查找一遍范围都会缩小一半,大大提高了检索的速度。
		 */
		int [] arr= {9,5,2,7,11,3,6};
		//二分查找的前提是数组中的元素必须是有序的,否则无法查找
		Arrays.sort(arr);//先对数组就行排序操作
		//2, 3, 5, 6, 7, 9, 11  排序后的元素
		int index = getFind(arr, 7);
		System.out.println(index);//运行结果  4
		
		System.out.println("----------------");
		int index2 = getFind(arr, 12);
		System.out.println(index2);//运行结果  元素 12 不存在  -1

	}
	
	//定义函数方法,传入要查找的数组和数
	public static int getFind(int[] arr,int a) {
		int max=arr.length-1;//第一次查找时的最大下标
		int min=0;//第一查找时的最小下标
		int mid=(max+min)/2;//中间数,用中间去找到值
		
		while (arr[mid]!=a) {//当中间的下标所对应的值不等于它本身时才继续循环,否则返回mid
			if(max>=min) {//最大下标要大于或等于最小下标,防止元素不存在时发生的错误
				//当查找的值小于中间下标对应的数时,就证明查找的数在中间下标所对应的数之前,所以下次循环的初始最大下标等于mid-1;
				if(arr[mid]>a) {
					max=mid-1;
				}
				//当查找的值大于中间下标对应的数时,就证明查找的数在中间下标所对应的数之后,所以下次循环的初始最小下标等于mid+1;
				if(arr[mid]<a) {
					min=mid+1;
				}
				mid=(max+min)/2;//每次循环都得到一个新的中间的下标
			}else {
				System.out.println("元素 "+a+" 不存在");
				mid=-1;//当没查到元素时返回-1,并结束循环
				break;//结束循环,避免无限执行循环
			}
		}
		
		return mid;//循环结束后返回查找的元素所对应的下标
	}
}

原文链接:https://blog.csdn.net/qq_43711597/article/details/114703325



所属网站分类: 技术文章 > 博客

作者:天使的翅膀

链接:http://www.javaheidong.com/blog/article/114225/5e3dd3c235d3af15680a/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

23 0
收藏该文
已收藏

评论内容:(最多支持255个字符)