二分查找的常规实现及自定义实现

逃离我推掉我的手 2022-10-14 00:43 170阅读 0赞

1、对应自增的数组，从中查到某个值或者下标，我们通常可以采取二分查找的算法，时间复杂度为logn。

比如从数组

int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

中判断7是否存在，下标多少；

代码示例：

public class BinarySearch {
    
    	public static void main(String[] args) {
    		int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };// 源数据
    		 
    		int key = 10;
    		//int ret = biSearch(arr, key);
    	//	int ret = twoSearch(arr, key);
     
    		System.out.println(ret);
    	}
    
    	private static int twoSearch(int[] arr, int a) {
    		int start = 0;
    		int len = arr.length - 1;
    		int mid;
    		while (len >= start){
    			mid = (len + start)/2;
    			if(arr[mid] < a){
    				start = mid + 1;//赋值下一个下标
    			}else if(arr[mid] > a){
    				len = mid - 1;//赋值前一个下标
    			}else {
    				return arr[mid];
    			}
    		}
    		return -1;
    	}
    
    
    	public static int biSearch(int arr[], int a) {
    		int start = 0;
    		int end = arr.length - 1;
    		int mid;
    		while (start <= end) {
    			mid = (start + end) / 2;
    			if (arr[mid] < a) {
    				start = mid + 1;
    			} else if (arr[mid] > a) {
    				end = mid - 1;
    			} else {
    				return mid;
    			}
    		}
    		return -1;//找不到
    	}
    }

2、对应部分自增的 变种，我们也可以采用二分查找的思想，时间复杂度当然也是logn。

比如从数组

int cusArr[] = {6, 7, 8, 9, 10,1, 2, 3, 4, 5};// 扩展源数据

中找到最大的数，并返回；

测试代码：

public class BinarySearch {
    
    	public static void main(String[] args) {
    	 
    		int cusArr[] = {6, 7, 8, 9, 110,1, 2, 3, 4, 5};// 扩展源数据
    		int key = 10;
    		int ret = cusTwoSearch(cusArr);
    		System.out.println(ret);
    	}
    
    	private static int cusTwoSearch(int[] cusArr) {
    		int maxIndex = 0;
    		int len = cusArr.length - 1;
    		int mid;
    		while (len >= maxIndex){
    			mid = (len + maxIndex)/2;
    			if (cusArr[mid] > cusArr[maxIndex]){
    				maxIndex = mid;//直接赋当前的下标，因为需要此下标的值参与对比
    			}else if (cusArr[mid] < cusArr[maxIndex]){
    				len = mid;//直接赋当前的下标，因为需要此下标的值参与对比
    			}else {
    				//return cusArr[maxIndex];//返回最大的值
    				return maxIndex;//返回最大值的下标
    			}
    		}
    		return -1;
    	}
     
    }

这就是二分查找的两种实现方式，平日还会遇到类似的需求，但是万变不离其宗，核心思想都是一致的，多写、多练、多思考，水平很快就提高了。