二分查找法应用

痛定思痛。 2023-06-28 11:28 42阅读 0赞

二分查找法：在一组数据（数值）中查找某个值是否存在时，为优化效率采取将数据分段（以中间值为节点一分为二），在段落中匹配值（若值匹配在某段落范围则将该段落再次一分为二，继续查找数值位置，直到找到为止），减少查询次数，提高查询返回时间。【数据越多越能体现二分查找法的优化效率，数据较少时二分查找法效率反而较低。】

二分查找法的概念请自行查找（百度上一堆），下面代码是个人在项目中对二分查找法的一个应用，当做个人笔记，方便复习。

条件：订单运费为阶梯价类型，根据订单重量匹配订单运费。

/**计算阶梯价类型订单价格*/
    	private static TransportationPriceAdvance queryPriceAdvance(List<TransportationPriceAdvance> list,BigDecimal orderWeight){
    		//startIndex:起始值，midIndex中间值，endIndex节点值
    		int startIndex=0,midIndex=0,endIndex=list.size();
    		TransportationPriceAdvance orderPrice = new TransportationPriceAdvance();
    		while (true){
    			midIndex = (endIndex+startIndex)/2;
    			int result =list.get(midIndex).getFristWeight().compareTo(orderWeight);
    			if(0==midIndex){
    				if(result!=-1){
    					//todo 当前重量小于阶梯最小重量返回阶梯最小重量
    					orderPrice=list.get(midIndex);
    				}
    				break;
    			}else{
    				if(0==result){
    					//todo 阶梯价重量等于订单重量返回对应价格
    					orderPrice =list.get(midIndex);
    					break;
    				}else if(1==result){
    					//todo 中间值重量大于订单重量
    						//todo 判断左侧最后一个值与订单重量的大小
    					int leftLastResult =list.get(midIndex-1).getFristWeight().compareTo(orderWeight);
    						if(0==leftLastResult){
    							//todo 等于返回左侧最后一个值
    							orderPrice =list.get(midIndex-1);
    							break;
    						}else if(-1==leftLastResult){
    							//todo 小于在即当前中间值重量是大于订单重量的最小值==》返回该值
    							orderPrice =list.get(midIndex);
    							break;
    						}else {
    							//todo 大于即向左查询
    							endIndex = midIndex;
    						}
    				}else if(-1==result){
    					//todo 中间值重量小于订单重量向右查询
    					startIndex =midIndex;
    				}
    			}
    		}
    		return orderPrice;
    	}

@Override
    	public AjaxResult feetrail(Integer companyType, String transportChannel, String countryCode, String weghit) {
    		AjaxResult ajaxResult = AjaxResult.error("操作异常");
    		try {
    			TransportationPriceAdvance priceAdvance = new TransportationPriceAdvance();
    			priceAdvance.setTransportCompanyType(companyType.toString());
    			priceAdvance.setTransportChannel(transportChannel);
    			priceAdvance.setCountry(countryCode);
    			priceAdvance.setDelStatus("N");
    			//获取对应的价格配置
    			List<TransportationPriceAdvance> list = selectTransportationPriceAdvanceList(priceAdvance);
    			if(null != list && list.size()>0){
    				String priceType = list.get(0).getPriceType();
    				BigDecimal orderWeghit = new BigDecimal(weghit);
    				switch (priceType){
    					case "1" :
    						//todo 续重处理
    						priceAdvance = list.get(0);
    						if(priceAdvance.getMaxWeight().compareTo(orderWeghit)==-1){
    							//todo 订单重量大于该渠道最大重量
    							ajaxResult.put("msg","订单重量超出该渠道最大限重【限重："+priceAdvance.getMaxWeight().setScale(2)+"】");
    						}else{
    							ajaxResult = AjaxResult.success("操作成功");
    							JSONObject object = new JSONObject();
    							object.put("timeFrame",priceAdvance.getTimeFrame()+"天");
    							//todo 计算费用
    							if(priceAdvance.getFristWeight().compareTo(orderWeghit)==-1){
    								//todo 大于首重，计算续费重
    								//获取需要计算的续重重量
    								BigDecimal continuousWeight = orderWeghit.subtract(priceAdvance.getFristWeight());
    								//获取续费价格
    								BigDecimal continuousPrice = continuousWeight.divide(priceAdvance.getContinuousWeight(),0,RoundingMode.UP).multiply(priceAdvance.getContinuousPrice());
    								//获取实际费用
    								object.put("orderPrice",continuousPrice.add(priceAdvance.getFristPrice()));
    							}else{
    								//todo 小于于首重，返回初始费用
    								object.put("orderPrice",priceAdvance.getFristPrice());
    							}
    							ajaxResult.put("data",object);
    						}
    						break;
    					case "2":
    						//todo 阶梯处理
    						//根据阶梯重量升序排序
    						list.sort(Comparator.comparing(TransportationPriceAdvance::getFristWeight));
    						//判断订单重量是否超过最大重量
    						if(list.get(list.size()-1).getFristWeight().compareTo(orderWeghit)== -1){
    							ajaxResult.put("msg","订单重量超出该渠道最大限重【限重："+list.get(list.size()-1).getFristWeight().setScale(2)+"】");
    						}else{
    							ajaxResult = AjaxResult.success("操作成功");
    							JSONObject object = new JSONObject();
    							TransportationPriceAdvance advance = queryPriceAdvance(list,orderWeghit);
    							object.put("timeFrame",advance.getTimeFrame()+"天");
    							object.put("orderPrice",advance.getFristPrice());
    							ajaxResult.put("data",object);
    						}
    						break;
    					default:
    						ajaxResult.put("msg","该渠道维护中暂不支持费用查询！");;
    
    				}
    			}else{
    				ajaxResult.put("msg","该渠道暂不支持费用查询！");
    			}
    		}catch (Exception e){
    			logger.info("操作异常",e);
    		}
    		return ajaxResult;
    	}