首頁 >Java >java教程 >java二分法查找怎麼實現

java二分法查找怎麼實現

angryTom
angryTom原創
2020-02-17 15:36:264519瀏覽

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