二分查找（折半查找）

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

介绍

• 二分查找排序英文名为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、重复以上步骤，直到找到目标元素或者搜索范围为空（找不到目标值）

代码

• 循环方法

  public static void main(String[] args) {int[] arr = {1,10, 20, 30, 40, 50, 60, 70, 80, 90};sort(arr,60);sort(arr,45);sort(arr,1);
  }public static int sort(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;}else if(arr[mid]<target){ // 目标值比中间值大，要往右边查找left = mid+1;}else{    // 目标值比中间值小，要往左边查找right = mid-1;}}System.out.println("没有该数值");return -1;
  }
  ------------输出结果--------------
  找到了【60】，位置是：6
  数值【45】不存在
  找到了【1】，位置是：0
  

• 递归方法

  public static void main(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);
  }
  public static int digui(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;}else if(arr[mid]>target){ // 目标值比中间值小return digui(arr,target,left,mid-1);}else{return digui(arr,target,mid+1,right);}
  }
  ------------输出结果--------------
  找到了【60】，位置是：6
  数值【45】不存在
  找到了【1】，位置是：0
  

老规矩，来个流程图

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

时间复杂度

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