二分查找算法模板-BinarySearch

叁歲伎倆 2024-04-06 10:26 53阅读 0赞

分为两种：

1、二分找指定值

2、先逆二分找边界再二分找指定值

package com.xch1.binary;
    
    public class Main1 {
    
    	// 二分查找（范围渐小）
    	// 1、建模：划分蓝红区域
    	// 2、确定返回LorR
    	// 3、套模板
    
    	// 找到第一个>=5的元素
    	public static int f1(int[] arr) {
    		int l = -1, r = arr.length;
    		while (l + 1 != r) {
    			int m = (l + r) / 2;
    			if (arr[m] >= 5) {
    				r = m;
    			} else {
    				l = m;
    			}
    		}
    		if (r == arr.length) {
    			return -1;
    		} else {
    			return r;
    		}
    	}
    
    	// 找到最后一个<5的元素
    	public static int f2(int[] arr) {
    		int l = -1, r = arr.length;
    		while (l + 1 != r) {
    			int m = (l + r) / 2;
    			if (arr[m] < 5) {
    				l = m;
    			} else {
    				r = m;
    			}
    		}
    		return l;
    	}
    
    	// 找到第一个>5的元素
    	public static int f3(int[] arr) {
    		int l = -1, r = arr.length;
    		while (l + 1 != r) {
    			int m = (l + r) / 2;
    			if (arr[m] > 5) {
    				r = m;
    			} else {
    				l = m;
    			}
    		}
    		if (r == arr.length) {
    			return -1;
    		} else {
    			return r;
    		}
    	}
    
    	// 找到最后一个<=5的元素
    	public static int f4(int[] arr) {
    		int l = -1, r = arr.length;
    		while (l + 1 != r) {
    			int m = (l + r) / 2;
    			if (arr[m] <= 5) {
    				l = m;
    			} else {
    				r = m;
    			}
    		}
    		return l;
    	}
    
    	// 二分延伸：外拓（范围渐大）
    	// 一般是确定右边界
    	// 左边界可以逆序即可变为右边界
    
    	// 找到第一个>=5的元素
    	public static int f5(int[] arr) {
    		// 先确定边界
    		int l = -1, r;
    		int p = 1;// 外拓指针
    		while (arr[p - 1] < 5) {
    			l = p - 1;
    			p *= 2;
    		}
    		r = p - 1;
    		// 再套模板
    		while (l + 1 != r) {
    			int m = (l + r) / 2;
    			if (arr[m] >= 5) {
    				r = m;
    			} else {
    				l = m;
    			}
    		}
    		return r;
    	}
    
    	// 找到最后一个<5的元素
    	public static int f6(int[] arr) {
    		// 先确定边界
    		int l, r = -1;
    		int p = arr.length - 1;// 外拓指针
    		while (arr[p] >= 5) {
    			r = p;
    			p /= 2;
    		}
    		l = p;
    		// 再套模板
    		while (l + 1 != r) {
    			int m = (l + r) / 2;
    			if (arr[m] < 5) {
    				l = m;
    			} else {
    				r = m;
    			}
    		}
    		return l;
    	}
    
    	// 找到第一个>5的元素
    	public static int f7(int[] arr) {
    		// 先确定边界
    		int l = -1, r;
    		int p = 1;// 外拓指针
    		while (arr[p - 1] <= 5) {
    			l = p - 1;
    			p *= 2;
    		}
    		r = p - 1;
    		// 再套模板
    		while (l + 1 != r) {
    			int m = (l + r) / 2;
    			if (arr[m] > 5) {
    				r = m;
    			} else {
    				l = m;
    			}
    		}
    		return r;
    	}
    
    	// 找到最后一个<=5的元素
    	public static int f8(int[] arr) {
    		// 先确定边界
    		int l, r = -1;
    		int p = arr.length - 1;
    		while (arr[p] > 5) {
    			r = p;
    			p /= 2;
    		}
    		l = p;
    		// 再套模板
    		while (l + 1 != r) {
    			int m = (l + r) / 2;
    			if (arr[m] <= 5) {
    				l = m;
    			} else {
    				r = m;
    			}
    		}
    		return l;
    	}
    	
    	public static void main(String[] args) {
    		int[] arr = { 1, 2, 3, 5, 5, 5, 8, 9 };
    		System.out.println(f1(arr));// 输出下标3
    		System.out.println(f2(arr));// 输出下标2
    		System.out.println(f3(arr));// 输出下标6
    		System.out.println(f4(arr));// 输出下标5
    
    		System.out.println(f5(arr));// 输出下标3
    		System.out.println(f6(arr));// 输出下标2
    		System.out.println(f7(arr));// 输出下标6
    		System.out.println(f8(arr));// 输出下标5
            
    	}
    
    }

二分查找模板应用思路：

![82d1861dc30141839f2aa5d589ad94ae.png][]

[82d1861dc30141839f2aa5d589ad94ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/dc47448cef0e4a468c93cc0b40fd5176.png