[算法详解] 二分查找算法及其变种(查找第一个数字/查找最后一个数字)

浅浅的花香味﹌ 2022-12-27 07:51 184阅读 0赞

### 前言 ###

> Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…  
> 思路很简单，细节是魔鬼 - - -Knuth

昨天做`Offer37-数字在排序数组内出现的次数`时候, 遇到了二分查找问题. 正好，借此机会总结一下。

前提条件: `数组是有序数组`

算法思路很简单：

*  声明`front`和`end`两个`index`.
 *  计算`mid`的index.
 *  根据`array[mid]`与`target`的值进行比较. 进行下一步的判断.

public static void binarySearch(int []array,int targetNumber){
    	int front = 0;
    	int end = array.length-1;
    	while(...){
    		int mid = (front+end)/2;
    		if(array[mid]==target){
    			...
    		}else if(array[mid]>target){
    			...
    		}else if(array[mid]<target){
    		    ...
    		}
    	}
    }

--------------------

### 二分查找-标准写法 ###

/**
    	 * 查找元素出现的位置（第一个搜索到的元素的下标）。二分查找算法。
    	 * 
    	 * */
    	public static int simpleBinarySearch(int []array,int targetNumber) {
    		int front = 0; // 注意0
    		int end = array.length-1;
    		int resultIndex = -1; 
    		while(front<=end) { //1. 注意1
    			int mid = (front+end)/2; //2. 注意2
    			if(array[mid]==targetNumber) {
    				resultIndex = mid; // 3. 注意3
    				break;
    			}else if(array[mid]>targetNumber) {
    				end = mid-1; // 4. 注意4
    			}else if(array[mid]<targetNumber) {
    				front = mid+1; // 5. 注意5
    			}
    		}
    		return resultIndex;
    	}

*  注意点0 - 注意`front`与`end`的初始下标。  
    因为在`Java`内, 数组的下标从`0`开始, 到`length-1`结束。所以定义的时候也需要注意一下这一点。

> Ex1. 数组内有多个元素 \{1,2,3\} / front=0,end=2;  
> Ex2. 数组内只有一个元素\{1\} / front=0,end=0;  
> Ex3. 数组内没有元素\{\} / front=0, end=-1;

*  注意点1 - `while(front<=end)` 注意循环结束条件，特别是这个等于号。  
    因为当`front==end`的时候，非常可能就是你的节点位置。

> Ex1. 数组内只有一个元素\{1\} / front=0, end=0; 需要找的数字为1  
> Ex2. 数组内有多个元素\{1,2,3\} target=3  
> front=0, end=2; mid=1; 变化 front=mid+1=2; end=2;  
> front=2, end=2; mid=2; 找到数字。  
> 以上2个例子当`front<end`的时候结束循环的时候, 都会出现异常。

*  注意点2 - `int mid = (front+end)/2;` `mid`的值的计算。

> 1.注意在Java内`(1+2)/2=1;` 不是1.5  
> 2. 变种写法 `int mid = front+(end-front)/2;`  
> 3. 变种写法-位运算 `int mid = (front+end)>>1;`

*  注意点3 - `if(array[mid]==targetNumber) {resultIndex = mid;break;}`

> 因为本方法只要求 寻求第一个找到的数字即可。而非其他要求。(其他要求见下文)

*  注意点4/5 - `front`与`end`的值的变化

else if(array[mid]>targetNumber) {
    				end = mid-1; // 4. 注意4
    			}else if(array[mid]<targetNumber) {
    				front = mid+1; // 5. 注意5
    			}

为什么不选择`end=mid`/`front=mid`呢？

> 1.  因为这样可能会导致某些情况出现死循环的情况。  
>     Ex1. \{1,2,3,4,5\} target=4  
>     当front=2,end=3,mid=2; 如果此时符合if(array\[mid\]<targetNumber) \{front=mid;\}  
>     那么程序会陷入死循环。永远无法获取结果。
> 2.  `end = mid-1;`/`front = mid+1;` 可以导致一些边界情况，结束循环。  
>     end=0-1=-1； front=length-1+1=length；的情况 特别注意这2个地方可能会导致数组的越界异常。

--------------------

### 二分查找算法 - 变种-查找第一个数字 ###

*  当数组内的数字重复的时候，我们有时候会有查找第一个或者最后一个出现数字的需求。`比如插入算法，需要维持算法的稳定性。binaryInsert()`

> Ex. \{1,2,3,3,3,3,4\} target=3 查找第一个数字 / 查找最后一个数字

##### 查找第一个数字 #####

/**
    	 * 获取第一个数字获取的下标Index。
    	 * 
    	 * */
    	public static int binarySearchOfFirstK(int []array,int targetNumber) {
    		int resultIndex = -1; 
    		int length = array.length;
    		int front = 0;
    		int end = array.length-1;
    		while(front<=end) {
    			int mid = (front+end)/2;
    			if(array[mid]==targetNumber) {
    				resultIndex = mid;
    				// 因为要向前走，寻找第一个元素
    				end = mid-1;
    			}else if(array[mid]>targetNumber) {
    				end = mid-1;
    			}else if(array[mid]<targetNumber) {
    				front = mid+1;
    			}
    		}
    		return resultIndex;
    	}
    	/**
    	 * 寻找第一个数字。查询结果优化。
    	 * 
    	 * */
    	public static int binarySearchOfFirstKOptimizing(int []array,int targetNumber) {
    		int resultIndex = -1; 
    		int length = array.length;
    		int front = 0;
    		int end = array.length-1;
    		while(front<=end) {
    			int mid = (front+end)/2;
    			if(array[mid]==targetNumber) {
    				if(((mid)>0&&array[mid-1]!=targetNumber)||mid==0) {
    					resultIndex = mid;
    					break;
    				}else {
    					end = mid-1;
    				}
    			}else if(array[mid]>targetNumber) {
    				end = mid-1;
    			}else if(array[mid]<targetNumber) {
    				front = mid+1;
    			}
    		}
    		return resultIndex;
    	}

通过上面可以看出。基本与二分查找如出一辙。但是注意`array[mid]==target`的时候的判断操作。

*  普通做法  
    `resultIndex = mid;end = mid-1;` 或者最后进行判断也可[你真的会写二分查找吗][Link 1]
 *  优化做法

if(array[mid]==targetNumber) {
    				if(((mid)>0&&array[mid-1]!=targetNumber)||mid==0) {
    					resultIndex = mid;
    					break;
    				}else {
    					end = mid-1;
    				}
    			}

因为判断了`mid-1`的前一位是否也等于`target`。  
如果是否，则表示当前已经是最大位了。无需再向前判断了。  
或者`mid==0`表示已经到了数组最头部了，也无需再判断了。

> PS: 2020-12-20 发现之前的数组边界条件写错了。重新理解一下。  
> 之前这边 `if(((mid+1)>=0&&array[mid-1]!=targetNumber)||mid==0) {`  
> 其实就是判断array\[mid\]前一位不等于target 或者 mid==0的情况。进行结束循环。  
> 所以这边array\[mid-1\] 保证 (mid-1)>=0数组不越界即可。
> 
>  *  防止数组左越界  
>     array\[mid-1\] -> mid-1>=0 mid>=1 mid>0  
>     `mid>0`
>  *  防止数组右越界  
>     array\[mid+1\] -> mid+1<=length-1 mid+1<length mid<length-1  
>     `mid<length-1`

##### 查找最后一个数字 #####

/**
    	 * 获取最后一个数字获取的下标Index。
    	 * 
    	 * */
    	public static int binarySearchOfLastK(int []array,int targetNumber) {
    		int resultIndex = -1; 
    		int length = array.length;
    		int front = 0;
    		int end = array.length-1;
    		while(front<=end) {
    			int mid = (front+end)/2;
    			if(array[mid]==targetNumber) {
    				resultIndex = mid;
    				// 因为要向后走，寻找最后一个元素
    				end = mid+1;
    			}else if(array[mid]>targetNumber) {
    				end = mid-1;
    			}else if(array[mid]<targetNumber) {
    				front = mid+1;
    			}
    		}
    		return resultIndex;
    	}
    	
    	/**
    	 * 查找最后一个元素下标。-优化
    	 * 
    	 * */
    	public static int binarySearchOfLastKOptimizing(int []array,int targetNumber) {
    		int resultIndex = -1; 
    		int length = array.length;
    		int front = 0;
    		int end = array.length-1;
    		while(front<=end) {
    			int mid = (front+end)/2;
    			if(array[mid]==targetNumber) {
    				if(((mid+1)<array.length&&array[mid+1]!=targetNumber) || mid+1==array.length) {
    					resultIndex = mid;
    					break;
    				}else {
    					end = mid+1;
    				}
    			}else if(array[mid]>targetNumber) {
    				end = mid-1;
    			}else if(array[mid]<targetNumber) {
    				front = mid+1;
    			}
    		}
    		return resultIndex;
    	}

实现策略和优化策略同上。

--------------------

### JDK内的实现BinarySort ###

/**
         * Sorts the specified portion of the specified array using a binary
         * insertion sort.  This is the best method for sorting small numbers
         * of elements.  It requires O(n log n) compares, but O(n^2) data
         * movement (worst case).
         *
         * If the initial part of the specified range is already sorted,
         * this method can take advantage of it: the method assumes that the
         * elements from index {@code lo}, inclusive, to {@code start},
         * exclusive are already sorted.
         *
         * @param a the array in which a range is to be sorted
         * @param lo the index of the first element in the range to be sorted
         * @param hi the index after the last element in the range to be sorted
         * @param start the index of the first element in the range that is
         *        not already known to be sorted ({@code lo <= start <= hi})
         * @param c comparator to used for the sort
         */
        @SuppressWarnings("fallthrough")
        private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                           Comparator<? super T> c) {
            assert lo <= start && start <= hi;
            if (start == lo)
                start++;
            for ( ; start < hi; start++) {
                T pivot = a[start];
    
                // Set left (and right) to the index where a[start] (pivot) belongs
                int left = lo;
                int right = start;
                assert left <= right;
                /*
                 * Invariants:
                 *   pivot >= all in [lo, left).
                 *   pivot <  all in [right, start).
                 */
                while (left < right) {
                    int mid = (left + right) >>> 1;
                    if (c.compare(pivot, a[mid]) < 0)
                        right = mid;
                    else
                        left = mid + 1;
                }
                assert left == right;
    
                /*
                 * The invariants still hold: pivot >= all in [lo, left) and
                 * pivot < all in [left, start), so pivot belongs at left.  Note
                 * that if there are elements equal to pivot, left points to the
                 * first slot after them -- that's why this sort is stable.
                 * Slide elements over to make room for pivot.
                 */
                int n = start - left;  // The number of elements to move
                // Switch is just an optimization for arraycopy in default case
                switch (n) {
                    case 2:  a[left + 2] = a[left + 1];
                    case 1:  a[left + 1] = a[left];
                             break;
                    default: System.arraycopy(a, left, a, left + 1, n);
                }
                a[left] = pivot;
            }
        }

*  注
 *  其中的判断条件还没有想明白。To Be continue.

--------------------

### Others ###

为什么每次只取中间值，而不是取2/3，或者0.618这样的黄金数字呢？

> 个人认为二分应该是普通效率最高的一种做法。时间复杂度为O(log2N)

--------------------

### Reference ###

\[1\]. [剑指Offer-JZ37][Offer-JZ37]  
\[2\]. [详解二分查找算法][Link 2]  
\[3\]. [你真的会写二分查找吗][Link 1]  
\[4\]. [百度百科-二分查找][-]  
\[5\]. [程序员，你应该知道的二分查找算法][Link 3]

[Link 1]: https://www.cnblogs.com/luoxn28/p/5767571.html
[Offer-JZ37]: https://www.nowcoder.com/ta/coding-interviews
[Link 2]: https://www.cnblogs.com/kyoner/p/11080078.html
[-]: https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/10628618?fr=aladdin
[Link 3]: https://juejin.cn/post/6844903911334101005