当前位置：首页 > news >正文

二分查找（折半查找）

news 2025/7/6 11:10:46

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

介绍

二分查找排序英文名为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