Home >Java >javaTutorial >How to implement binary search in java
How to implement binary search in java
BinarySearch
Binary search, as the name implies, is to Divide the data into two parts each time and then find the data you want.
We can think of it this way. Binary search is very similar to the price guessing game we usually play. When you quote a price The referee will tell you how high or low the price is relative to the true value. If it is lower, we will definitely give you a slightly higher price, and vice versa.
(Related video tutorial sharing: java video tutorial)
During binary search, the incoming data must be in order. Assume that it is in ascending order now, and then each Compare the value you are looking for with the middle value (left border of the array (right border - left border)/2). If it is larger, it will look for the data on the left side of the middle value. If it is smaller, it will look for the data on the right side of the middle value.
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("您所查找的数据不存在"); } } }
For more java tutorials, please pay attention to the Java tutorial column of the PHP Chinese website.
The above is the detailed content of How to implement binary search in java. For more information, please follow other related articles on the PHP Chinese website!