有序数组的二分查找---查找元素第一次和最后一次出现的位置

桃扇骨 2024-04-19 08:09 63阅读 0赞

public class Main {
     
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] a={3,5,10,10,10,13,13,19,23};
    		System.out.println(first(a,10));
    		System.out.println(last(a,10));
    		System.out.println();
    		System.out.println(binsearch_low(0,a.length-1,10,a));
    		System.out.println(binsearch_up(0,a.length-1,10,a));
    	}
     
    	private static int last(int[] a, int key) {
    		int min=0,max=a.length-1;
    		int mid=0;
    		while(min<=max){
    			mid=(max+min+1)/2;
    			if (key>=a[mid]) {
    				min=mid;
    			}else {
    				max=mid-1;
    			}
    			if (max==min) {
    				break;
    			}
    		}
    		if (a[max]!=key) {//当查找元素不存在时，返回-1
    			return -1;
    		}else {
    			return max;
    		}
    	}
     
    	private static int first(int[] a, int key) {
    		// TODO Auto-generated method stub
    		int min=0,max=a.length-1;
    		int mid=0;
    		while(min<=max){
    			mid=(max+min)/2;
    			if (key>a[mid]) {
    				min=mid+1;
    			}else {
    				max=mid;
    			}
    			if (max==min) {
    				break;
    			}
    		}
    		if (a[min]!=key) {//当查找元素不存在时，返回-1
    			return -1;
    		}else {
    			return min;
    		}
    	}
    	//上界：
    	public static int binsearch_low(int lef, int rig,int key,int a[])
    	{
    	    int ans = -1;
    	    int low = lef,high = rig;
    	    while(low <= high){
    	        int mid = (low + high)/2;
    	        if(key == a[mid]){
    	            ans = mid;
    	            high = mid - 1;
    	        }
    	        else if(key < a[mid])
    	            high = mid - 1;
    	        else
    	            low = mid + 1;
    	    }
    	    return ans;
    	}
    	 
    	 
    	 
    	//下界：
    	public static int binsearch_up(int lef, int rig,int key,int a[])
    	{
    	    int ans = -1;
    	    int low = lef,high = rig;
    	    while(low <= high){
    	        int mid = (low + high)/2;
    	        if(key == a[mid]){
    	            ans = mid;
    	            low = mid + 1;
    	        }
    	        else if(key < a[mid]){
    	            high = mid - 1;
    	        }
    	        else{
    	            low = mid + 1;
    	        }
    	    }
    	    return ans;
    	}
    }

最先出现和最后出现合并【小伙伴的代码，觉得很简洁，值得学习`在这里插入代码片`

package searching;
     
    public class BinarySearchFL {
    	
    	public static void main(String[] args) {
    		int[] a={10,10,10,10,10,13,13,19,23};
    		System.out.println(binarySearch(a, 13, 0));
    	}
    	
    	/**
    	 * @param a 待查数组
    	 * @param key 待查关键字
    	 * @param flag	如果flag等于0，表示查找关键字出现的第一个位置；如果flag等于1，返回关键字出现的最后一个位置
    	 * @return 关键字的位置
    	 */
    	private static int binarySearch(int[] a, int key, int flag) {
    		int len = a.length;
    		if(key < a[0] || key > a[len - 1])
    			return -1;
    		
    		int i = 0, j = len - 1;
    		while(i <= j) {
    			int mid = (i + j) / 2;
    			if(key == a[mid]) {
    				//接下来的三行代码是为了查找关键字出现的最早的位置
    				int tmp = mid;
    				while(--tmp >= 0 && a[tmp] == key);//防止越界
    				i = tmp + 1;	//应该新定义一个变量表示，用i存储也行。
    				
    				//接下来的两行代码是为了查找关键字出现的最后的位置
    				while(++mid < len && a[mid] == key);
    				j = mid - 1;
    				
    				//返回找到的关键字
    				if(flag == 0) 
    					return i;
    				else 
    					return j;
    			}else if(key > a[mid]){
    				i = mid + 1;
    			}else {
    				j = mid - 1;
    			}
    		}
    		return -1;
    	}
    }