>Java >java지도 시간 >Java에서 이진 검색을 구현하는 방법

Java에서 이진 검색을 구현하는 방법

angryTom
angryTom원래의
2020-02-17 15:36:264533검색

Java에서 이진 검색을 구현하는 방법

Java에서 이진 검색을 구현하는 방법

BinarySearch#🎜 🎜 #

이진 검색은 이름에서 알 수 있듯이 데이터를 매번 두 부분으로 나눈 다음 원하는 데이터를 찾는 것입니다.

이진 검색이라고 생각하면 됩니다. 우리가 일반적으로 하는 가격 추측 게임에서 가격을 제시하면 심판이 실제 가격에 비해 가격이 얼마나 높거나 낮은지 알려줍니다. 만약 가격이 낮으면 우리는 확실히 약간 더 높은 가격을 제시합니다. 가격, 그 반대.

(관련 비디오 튜토리얼 공유:

java 비디오 튜토리얼)

이진 검색 중에는 들어오는 데이터를 순서대로 정렬해야 합니다. 오름차순으로 정렬한 다음 찾고 있는 값을 중간 값(배열의 왼쪽 경계선 + (오른쪽 경계선 - 왼쪽 경계선)/2)과 비교할 때마다 더 큰 경우에는 배열의 데이터를 찾습니다. 중간 값보다 왼쪽 값이 작을 경우, 중간 값보다 오른쪽 데이터를 찾습니다.

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)
			{
				//证明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<amount)
		{
			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("您所查找的数据不存在");
		}
	}
 
}

자세한 내용은

java 튜토리얼, PHP 중국어 웹사이트의 Java 튜토리얼 컬럼을 주목해 주세요.

위 내용은 Java에서 이진 검색을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.