java二分查找算法

我就是我 2024-03-27 13:24 57阅读 0赞

1.二分查找：

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

2.二分查找算法的思路

![在这里插入图片描述][1d4813cda55741eca2a50818beea9319.png]

3.二分查找的代码

说明：增加了找到所有的满足条件的元素下标:  
课后思考题： \{1,8, 10, 89, 1000, 1000，1234\} 当一个有序数组中，有多个相同的数值时，如何将所有的数值  
都查找到，比如这里的 1000.

import java.util.ArrayList;
    import java.util.List;
    
    //注意：使用二分查找的前提是该数组是有序的
    public class BinarySearch {
        
    
    	public static void main(String[] args) {
        
    //		int arr[] = {1,8, 10, 89, 1000, 1234};
    		int arr[] = {
         1, 8, 10, 89, 1000, 1000, 1234 };
    
    //		int resIndex = binarySearch(arr, 0, arr.length - 1, 89);
    //		System.out.println("resIndex=" + resIndex);
    
    		List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
    		System.out.println("resIndexList=" + resIndexList);
    	}
    
    	// 二分查找算法
    
    	/**
    	 * 
    	 * @param arr     数组
    	 * @param left    左边的索引
    	 * @param right   右边的索引
    	 * @param findVal 要查找的值
    	 * @return 如果找到就返回下标，如果没有找到就返回-1
    	 */
    	public static int binarySearch(int[] arr, int left, int right, int findVal) {
        
    		// 当left > right 时，说明递归整个数组但是没有找到
    		if (left > right) {
        
    			return -1;
    		}
    		int mid = (left + right) / 2;
    		int midVal = arr[mid];
    
    		if (findVal > midVal) {
        // 向右递归
    			return binarySearch(arr, mid + 1, right, findVal);
    
    		} else if (findVal < midVal) {
        // 向左递归
    			return binarySearch(arr, left, mid - 1, findVal);
    
    		} else {
        
    			return mid;
    		}
    
    	}
    	// 完成一个课后思考题:
    	/*
    	 * 课后思考题： {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) {
        
    		// 当left > right 时，说明递归整个数组但是没有找到
    		if (left > right) {
        
    			return new ArrayList<Integer>();
    		}
    		int mid = (left + right) / 2;
    		int midVal = arr[mid];
    
    		if (findVal > midVal) {
        // 向右递归
    			return binarySearch2(arr, mid + 1, right, findVal);
    
    		} else if (findVal < midVal) {
        // 向左递归
    			return binarySearch2(arr, left, mid - 1, findVal);
    
    		} else {
        
    			ArrayList<Integer> resIndexlist = new ArrayList<Integer>();
    			// 向 mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合 ArrayList
    			int temp = mid - 1;
    			while (true) {
        
    				if (temp < 0 || arr[temp] != findVal) {
        // 退出
    					break;
    				}
    				// 否则，就将temp放入到resIndexList
    				resIndexlist.add(temp);
    				temp -= 1;// temp左移
    			}
    			resIndexlist.add(mid);
    
    			// 向 mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合 ArrayList
    			temp = mid + 1;
    			while (true) {
        
    				if (temp > arr.length - 1 || arr[temp] != findVal) {
        // 退出
    					break;
    				}
    				// 否则，就将temp放入到resIndexList
    				resIndexlist.add(temp);
    				temp += 1;// temp右移
    			}
    
    			return resIndexlist;
    		}
    
    	}
    
    }

[1d4813cda55741eca2a50818beea9319.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/100d209877ac49e5b22ce7637631a76b.png