二分查找模板（查找数、左边界、右边界）

朱雀 2023-01-07 04:58 189阅读 0赞

## 二分查找模板（查找数、左边界、右边界） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

`Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...`

### 二分查找框架 ###

int binarySearch(int[] nums, int val) {
        
        int left = 0, right = ...;
        
        while(...) {
        
            int mid = left + (right - left) / 2;
            if(nums[mid] == val) {
        
                //...
            }else if(nums[mid] < val) {
        
                //...
            }else if(nums[mid] > val) {
        
                //...
            }
        }
        return ...;
    }

### 查找一个数val ###

int binarySearch(int[] nums, int val) {
        
    	int left = 0;
        int right = nums.length - 1;    //☚☚☚
        
    	while(left <= right) {
                  //☚☚☚
    		int mid = left + (right - left) / 2;
    		if(nums[mid] == val) {
        
    			return mid;       //☚☚☚
    		}else if(nums[mid] < val) {
        
    			left = mid + 1;
    		}else if(nums[mid] > val) {
        
    			right = mid - 1;
    		}
    	}
    	return -1;
    }

此算法的缺陷

*  若要在`[1, 2, 2, 2, 3]`中查找`2`，则返回的下标为`2`
 *  若为第一个则是下标`1`
 *  若为最后一个则是下标`3`

### 查找一个数val（返回第一次出现的下标） ###

#### 方法一： ####

int binarySearch(int[] nums, int val) {
        
        if(nums == null || nums.length == 0) return -1;
    	int left = 0;
    	int right = nums.length - 1;  //☚☚☚
        
    	while(left <= right) {
                //☚☚☚
    		int mid = left + (right - left) / 2;
    		if(nums[mid] == val) {
        
    			right = mid - 1;   //☚☚☚
    		}else if(nums[mid] < val) {
        
    			left = mid + 1;
    		}else if(nums[mid] > val) {
        
    			right = mid - 1;
    		}
    	}
    	return right + 1;   //☚☚☚
    }

简化代码为

...
    while(left <= right) {
        
    	int mid = left + (right - left) / 2;
    	if(nums[mid] < val) {
        
    		left = mid + 1;
    	}else {
        
    		right = mid - 1;
    	}
    }
    ...

#### 方法二： ####

int binarySearch(int[] nums, int val) {
        
    	if(nums == null || nums.length == 0) return -1;
    	int left = 0;
    	int right = nums.length;   //☚☚☚
    
    	while(left < right) {
        
    		int mid = left + (right - left) / 2;
    		if(nums[mid] == val) {
        
    			right = mid;     //☚☚☚
    		}else if(nums[mid] < val){
        
    			left = mid + 1;
    		}else if(nums[mid] > val){
        
    			right = mid;    //☚☚☚
    		}
    	}
    	return left;   //☚☚☚
    }

### 查找一个数val（返回最后一次出现的下标） ###

#### 方法一： ####

int binarySearch(int[] nums, int val) {
        
        if(nums == null || nums.length == 0) return -1;
    	int left = 0;
    	int right = nums.length - 1;  //☚☚☚
        
    	while(left <= right) {
                //☚☚☚
    		int mid = left + (right - left) / 2;
    		if(nums[mid] == val) {
        
    			left = mid + 1;   //☚☚☚
    		}else if(nums[mid] < val) {
        
    			left = mid + 1;
    		}else if(nums[mid] > val) {
        
    			right = mid - 1;
    		}
    	}
    	return left - 1;  //☚☚☚
    }

简化代码为

...
    while(left <= right) {
        
    	int mid = left + (right - left) / 2;
    	if(nums[mid] <= val) {
        
    		left = mid + 1;
    	}else {
        
    		right = mid - 1;
    	}
    }
    ...

#### 方法二： ####

int binarySearch(int[] nums, int val) {
        
    	if(nums == null || nums.length == 0) return -1;
    	int left = 0;
    	int right = nums.length;   //☚☚☚
    		
    	while(left < right) {
              //☚☚☚
    		int mid = left + (right - left) / 2;
    		if(nums[mid] == val) {
        
    			left = mid + 1;   //☚☚☚
    		}else if(nums[mid] < val){
        
    			left = mid + 1;   
    		}else if(nums[mid] > val){
        
    			right = mid;      //☚☚☚
    		}
    	}
    	return left - 1;    //☚☚☚
    }

### 左边界（返回小于val的最大值的下标） ###

同`查找一个数（返回第一次出现的下标）`思路一样，

找到第一次出现的下标`right + 1`后，下标`right`处就是小于它的最大值

int binarySearch(int[] nums, int val) {
        
        if(nums == null || nums.length == 0) return -1;
    	int left = 0;
    	int right = nums.length - 1;  
        
    	while(left <= right) {
                
    		int mid = left + (right - left) / 2;
    		if(nums[mid] == val) {
        
    			right = mid - 1;   
    		}else if(nums[mid] < val) {
        
    			left = mid + 1;
    		}else if(nums[mid] > val) {
        
    			right = mid - 1;
    		}
    	}
    	return right;   //☚☚☚
    }

### 右边界（返回大于val的最小值的下标） ###

同`查找一个数（返回最后一次出现的下标）`思路一样，

找到最后一次出现的下标`left - 1`后，下标`left`处就是大于它的最小值

int binarySearch(int[] nums, int val) {
        
        if(nums == null || nums.length == 0) return -1;
    	int left = 0;
    	int right = nums.length - 1;  
        
    	while(left <= right) {
                
    		int mid = left + (right - left) / 2;
    		if(nums[mid] == val) {
        
    			left = mid + 1;   
    		}else if(nums[mid] < val) {
        
    			left = mid + 1;
    		}else if(nums[mid] > val) {
        
    			right = mid - 1;
    		}
    	}
    	return left;  //☚☚☚
    }

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

上述代码`while`循环中分情况写全是为了便于理解，看懂就好，是否化简看个人喜好啦~