数组查找之二分查找注意事项

╰+攻爆jí腚メ 2022-02-09 10:21 212阅读 0赞

**给定一个数组，先排序，然后查找，这种做法对吗？**  
例如如下代码：

public class ArrayDemo2 {
    	public static void main(String[] args) {
    		//定义数组
    		int[] arr = {24,69,80,57,13};
    		
    		//先排序
    		
    		bubbleSort(arr);
    		System.out.println("排序后的数组为：");
    		printArray(arr);
    		
    		//后查找
    		int index = getIndex(arr, 24);
    		System.out.println("index:"+index);
    	}
    	
    	//遍历数组
    	public static void printArray(int[] arr) {
    		System.out.print("[");
    		for(int x = 0;x <arr.length;x++) {
    			if(x == arr.length-1) {
    				System.out.print(arr[x]);
    			}else{
    				System.out.print(arr[x]+", ");
    			}
    		}
    		System.out.println("]");
    	}
    	//冒泡排序功能
    	public static void bubbleSort(int[] arr) {
    		for(int x = 0;x < arr.length-1;x++) {
    			for(int y = 0;y < arr.length-1-x;y++) {
    				if(arr[y] > arr[y+1]) {
    					int temp = arr[y];
    					arr[y] = arr[y+1];
    					arr[y+1] = temp;
    				}
    			}
    		}
    	}
    	
    	//二分查找(折半查找)排序
    	public static int getIndex(int[] arr,int value) {
    		int min = 0;
    		int max = arr.length-1;
    		int mid = (min+max)/2;
    		
    		while(arr[mid] != value) {
    			if(arr[mid] > value) {
    				max = mid - 1;
    			}else if(arr[mid] < value) {
    				min = mid + 1;
    			}
    			
    			//加入判断：
    			if(min > max) {
    				return -1;
    			}
    			mid = (min+max)/2;
    		}
    		
    		return mid;
    	}
    }

注意：上面那种做法是有问题的！  
**因为数组本身是无序的，所以这种情况下不能使用二分查找。所以，如果你先对其进行排序，但是你排序的时候已经改变了我最原始的元素索引！**