二分查找（折半查找）

• 这次不排序了，对排好序的数组做个查找吧

介绍

• 二分查找排序英文名为BinarySort，是一种效率较高的查找方法
• 要求线性表必须采用顺序存储结构

基本思路

• 通过不断地将搜索范围缩小一半来找到目标元素： - 1、假定数组为arr，需要查找的值为target- 2、定义left、right 和mid三个索引。mid=(left+right)/2；- 3、如果中间元素正好是要查找的元素，搜索结束； （ 即arr[mid]==target，结束）- 4、如果目标元素大于中间元素，那么在数组的右半部分继续查找 （ 即arr[mid]>target，循环或者递归右半部分）- 5、如果目标元素小于中间元素，那么在数组的左半部分继续查找 （ 即arr[mid]<target，循环或者递归左半部分）- 6、重复以上步骤，直到找到目标元素或者搜索范围为空（找不到目标值）

代码

• 循环方法publicstaticvoidmain(String[] args){int[] arr ={1,10,20,30,40,50,60,70,80,90};sort(arr,60);sort(arr,45);sort(arr,1);}publicstaticintsort(int[] arr,int target){int left =0;int right = arr.length-1;while(left<=right){// 此处=是为了当索引移动后只剩一个时，也需要比较int mid =(left+right)/2;// 放在while循环外边就成了固定值了if(arr[mid]==target){System.out.println("找到了！");return mid;}elseif(arr[mid]<target){// 目标值比中间值大，要往右边查找 left = mid+1;}else{// 目标值比中间值小，要往左边查找 right = mid-1;}}System.out.println("没有该数值");return-1;}------------输出结果--------------找到了【60】，位置是：6数值【45】不存在找到了【1】，位置是：0
• 递归方法publicstaticvoidmain(String[] args){int[] arr ={1,10,20,30,40,50,60,70,80,90};digui(arr,60,0,arr.length-1);digui(arr,45,0,arr.length-1);digui(arr,1,0,arr.length-1);}publicstaticintdigui(int[] arr,int target,int left,int right){if(left>right){System.out.println("不存在该数值");return-1;}int mid =(left+right)/2;if(arr[mid]==target){System.out.println("找到了！");return mid;}elseif(arr[mid]>target){// 目标值比中间值小returndigui(arr,target,left,mid-1);}else{returndigui(arr,target,mid+1,right);}}------------输出结果--------------找到了【60】，位置是：6数值【45】不存在找到了【1】，位置是：0

老规矩，来个流程图

• 希望这三张图能帮忙大家理解为什么left<=right

时间复杂度

• 最好情况是O(1)，即一下就找到了
• 平均是O(logN)