资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

java的二分法查找是什么?怎么实现?-创新互联

什么是二分法查找:

创新互联建站是一家集网站建设,巴林左旗企业网站建设,巴林左旗品牌网站建设,网站定制,巴林左旗网站建设报价,网络营销,网络优化,巴林左旗网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。

二分法也就是折半查找,在有序的数列中查找指定的元素,设定最小索引(low)和大索引(height-1)还有中间值mid((low+height-1)/2),这种查找,如果中间值比指定元素小让low=mid+1,如果中间值比指定元素大,让height=mid-1;

代码实现:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
				int arr[] = { 2, 5, 6, 8, 9, 4, 7 };
				Arrays.sort(arr);
				int deix(索引) = getxiabiao(arr, 7);
				
			}
			public static int getxiabiao(int[] arr, int key) {
				int heigh = arr.length-1;
				int low = 0;
				int mid = 0;
				while (low <= heigh) {
					mid = low + (heigh - low)/2;
					if (arr[mid] == key) {
						return mid;
					} else if (arr[mid] < key) {
						low = mid + 1;
					} else if (arr[mid] > key) {
						heigh = mid - 1;
					}
				}
				return -1;
			}
		}

中间值的设定有两种方法;

算法一: mid = (low + high) / 2

算法二: mid = low + (high – low)/2

乍看起来,算法一简洁,算法二提取之后,跟算法一没有什么区别。但是实际上,区别是存在的。

算法一的做法,在极端情况下,(low + high)存在着溢出的风险,进而得到错误的mid结果,导致程序错误,而算法二能够保证计算出来的mid,一定大于low,小于high,不存在溢出的问题。

以上就是java实现二分法查找的详细内容,更多请关注创新互联其它相关文章!


本文题目:java的二分法查找是什么?怎么实现?-创新互联
文章源于:http://cdkjz.cn/article/cepioj.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220