二分算法几种应用和技巧

向右看齐 2022-10-19 15:59 71阅读 0赞

首先，我们使用二分算法来进行快速查找，二分算法适用于有序数组。

## 二分算法需要注意的点 ##

*  循环退出的条件是low<=high，而不是low<high。
 *  mid的取值是mid := low + (high - low ) >> 1，位运算进行除法。
 *  low和high的更新，low =mid +1，high =mid - 1。

## 二分算法的应用 ##

*  查找第一个与target相等的数
 *  查找最后一个与target相等的数
 *  查找第一个大于等于target的数
 *  查找最后一个小于等于target的数  
    **查找第一个与target相等的数**

func search ( nums []int , target int) int {
        
    	low , high := 0 , len(nums) - 1
    	for low <= high {
        
    		mid := low + ( (high - low ) >> 1 )
    		if target < nums[mid] {
        
    			high = mid - 1 
    		} else if target > nums[mid] {
        
    			low = mid + 1
    		} else {
        
    			if mid == 0 || nums[mid - 1 ] != target {
        
    				return mid
    			}
    			high = mid - 1
    		}
    	}
    	return -1
    }

**查找最后一个与target 相等的数**

func search (nums []int , target int) {
        
    	low , high := 0 , len(nums) - 1
    	for low <= high {
        
    		mid := low + (high - low ) >> 1
    		if nums[mid] > target {
        
    			high = mid - 1
    		} else if nums[mid] < target {
        
    			low = mid + 1
    		} else {
        
    			if mid == len(nums) - 1 || num[mid + 1] != target {
        
    				return mid
    			}
    			low = mid + 1
    		}
    	}
    	return -1
    }

**寻找第一个大于等于target的元素**

func search (nums []int , target int){
        
    	low , high := 0 , len(nums) - 1
    	for low <= high {
        
    		mid := low + (high - low) >> 1
    		if nums[mid] >= target {
        
    			if mid == 0 || nums[mid - 1] < target {
        
    				return mid
    			}
    			high = mid - 1
    		} else {
        
    			low = mid + 1
    		}
    	}
    	return -1
    }

**寻找最后一个小于等于target的元素**

func search (nums []int , target int){
        
    	low , high := 0 , len(nums) - 1
    	for low <= high {
        
    		mid := low + (high - low) >> 1
    		if nums[mid] <= target {
        
    			if mid == len(nums) - 1 || nums[mid + 1] > target {
        
    				return mid
    			}
    			low = mid + 1
    		} else {
        
    			high = mid - 1
    		}
    	}
    	return -1
    }

## 二分变法例子 ##

func peakindex(nums []int) int {
        
    	low , high := 0 , len(nums) - 1
    	for low < high {
        
    		mid := low + (high - low) >> 1
    		if nums[mid] > nums[mid + 1] {
        
    			high = mid - 1
    		} else {
        
    			low = mid + 1
    		}
    	}
    	return low
    }