java实现二分查找

柔光的暖阳◎ 2022-06-08 06:00 200阅读 0赞

**java实现二分查找**

**任意数组，先用快速排序进行排序，再二分查找给定数字**

>     public class Test02 {
>     	//记录查找的次数
>     	static int count = 0;
>     	public static void main(String[] args) {
>     		int[] nums={51,20,32,45,85,16,47};
>     		System.out.println("原数组：");
>     		print(nums);
>     		//快速排序
>     		quickSort(nums,0,nums.length-1);
>     		System.out.println("排序后数组：");
>     		print(nums);
>     		//折半查找（二分查找）
>     		int fNum = 2;
>     		count++;
>     		int n = binaryFind(nums,0,nums.length-1,fNum);
>     		if(n==-1){
>     			System.out.println("次数组不存在数字："+fNum);
>     		}else{
>     			System.out.println("要查找的数字为："+fNum);
>     			System.out.println("查找次数为："+count);
>     			System.out.println("下标为："+n);
>     		}
>     	}
>     
>     	private static int binaryFind(int[] nums, int start, int end, int key) {
>     		int middleNum = (end - start)/2 + start;
>     		if(key == nums[middleNum]){
>     			return middleNum;
>     		}
>     		if(start>end){
>     			return -1;
>     		}else if(key>nums[middleNum]){
>     			count++;
>     			return binaryFind(nums, middleNum+1, end, key);
>     		}else{
>     			count++;
>     			return binaryFind(nums, start, middleNum-1, key);
>     		}
>     	}
>     
>     	private static void quickSort(int[] nums, int start, int end) {
>     		int sStart = start;
>     		int eEnd = end;
>     		int key = nums[start];
>     		while(eEnd>sStart){
>     			while(eEnd>sStart && nums[eEnd]>=key){
>     				eEnd--;
>     			}
>     			if(nums[eEnd]<=key){
>     				int temp = nums[eEnd];
>     				nums[eEnd] = nums[sStart];
>     				nums[sStart] = temp;
>     			}
>     			while(eEnd > sStart && nums[sStart]<=key){
>     				sStart++;
>     			}
>     			if(nums[sStart]>=key){
>     				int temp = nums[sStart];
>     				nums[sStart] = nums[eEnd];
>     				nums[eEnd] = temp;
>     			}
>     		}
>     		if(sStart>start){
>     			quickSort(nums, start, sStart-1);
>     		}
>     		if(eEnd<end){
>     			quickSort(nums, eEnd+1, end);
>     		}
>     	}
>     
>     	private static void print(int[] nums) {
>     		for (int i : nums) {
>     			System.out.print(i+" ");
>     		}
>     		System.out.println();
>     	}
>     }
> 
>   
>   
>