我所知道的查找算法之二分查找法

vlambda
2020-04-29

我所知道的查找算法之二分查找法

作者前言

大家好,我是阿濠,今篇内容跟大家分享的是查找算法之二分查找法

一、介绍二分查找法

是一种在有序数组中查找某一特定元素的搜索算法。

1.搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索结束

2.如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且重新开始从中间元素进行比较。

3.如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二、示例认识线性查找算法

对有序数组进行二分查找{1, 8, 10, 89, 1000, 1234} 输入一个数，看看该数组是否存在此数并且求出下标，如果没有就提示"没有这个数"。

步骤思路
1.确定数组中间数的下标mid=(left+right)/2
2.将查询的数findValue和中间数arr[mid]进行比较
3.若findVale>arr[mid],则说明查找的数findValue在右边,进行递归向右查询
4.若findVale<arr[mid],则说明查找的数findValue在左边,进行递归向左查询
5.若findVale = =arr[mid],则说明查找的数已找到并返回下标

结束递归思路
1.找到findValue值结束递归
2.数组递归完仍未找到findValue也结束递归，当left>right结束递归退出

//二分查找算法/** * * @param arr 数组 * @param left 左边的索引 * @param right 右边的索引 * @param findVal 要查找的值 * @return 如果找到就返回下标，如果没有找到,就返回-1 */public static int binarySearch(int[] arr, int left, int right, int findVal) {
 //一、没有找到的情况 if(left > right){ return -1;    } //二、找到的情况 //中间下标 int mid = (left + right) / 2; int midVal =arr[mid];//中间下标对应的值
 if(findVal>midVal) { //若`findVale>arr[mid]`,则说明查找的数`findValue在右边`,进行递归`向右查询` return binarySearch(arr, mid + 1, right, findVal); }else if (findVal<midVal){ //若`findVale<arr[mid]`,则说明查找的数`findValue在左边`,进行递归`向左查询` return binarySearch(arr,left,mid-1,findVal); }else{ //若`findVale = =arr[mid]`,则说明`查找的数已找到并返回下标` return mid; }}

public static void main(String[ ] args) { int arr[]={ 1, 8, 10, 89, 1000, 1234}; int rearchIndex = binarySearch(arr,0,arr.length-1,8); if(rearchIndex == -1) { System. out. println("没有找到"); } else { System .out. println("找到，下标为=" + rearchIndex); }}运行结果如下：找到，下标为 = 1

三、数组中出现重复数值

有序数组：{1,8, 10, 89, 1000, 1000, 1234}，有多个相同的数值时，如何将所有的数值都查找到，比如这里的1000.

//二分查找算法/** * 课后思考题: {1,8， 10，89，1000， 1000， 1234} 当一个有序数组中, * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的1000 * * 思路分析 * 1.在找到mid 索引值，不要马上返回. * 2.向mid 索引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList * 3.向mid 索引值的右边扫描,将所有满足1000， 的元素的下标，加入到集合ArrayList * 4.将Arraylist返 回 */public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
 //一、没有找到的情况 if(left > right){ return new ArrayList<Integer>(); }
 //二、找到的情况 //中间下标 int mid = (left + right) / 2; int midVal =arr[mid];//中间下标对应的值
 if(findVal>midVal) { //若`findVale>arr[mid]`,则说明查找的数`findValue在右边`,进行递归`向右查询` return binarySearch2(arr, mid + 1, right, findVal); }else if (findVal<midVal){ //若`findVale<arr[mid]`,则说明查找的数`findValue在左边`,进行递归`向左查询` return binarySearch2(arr,left,mid-1,findVal); }else{ /**思路分析 * 1.在找到mid 索引值，不要马上返回. * 2.向mid 索引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList * 3.向mid 索引值的右边扫描,将所有满足1000， 的元素的下标，加入到集合ArrayList * 4.将Arraylist返回 * */ ArrayList<Integer> rearchIndexlist=new ArrayList<Integer>(); //向mid 索引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList int temp= mid - 1; while(true){ //证明向mid 索引值的左边扫描 没有找到相同的findValue值 if(temp < 0 || arr[temp] != findVal ){ break; } //证明有相同的findValue值，放入rearchIndexlist里 rearchIndexlist.add(temp); temp -= 1;//向左移 } //将找到的mid 索引值 放入rearchIndexlist 中 rearchIndexlist.add(mid);
 //向mid 索引值的右边扫描,将所有满足1000， 的元素的下标，加入到集合ArrayList temp= mid + 1; while(true){ //证明向mid 索引值的右边扫描 没有找到相同的findValue值 if(temp > arr.length -1 || arr[temp]!= findVal ){ break; } //证明有相同的findValue值，放入rearchIndexlist里 rearchIndexlist.add(temp); temp += 1;//向右移 } return rearchIndexlist; }}

public static void main(String[ ] args) {
 int arr[]={ 1, 10, 89, 1000, 1000, 1234};
 List integerList= binarySearch2(arr,0,arr.length-1,1000); System.out.println("找到的所有值："+ integerList); }
运行结果如下：找到的所有值:[3,4]