【二分查找】左侧边界、右侧边界、查找值

淩亂°似流年 2022-12-01 14:08 132阅读 0赞

> 一直以来，搞不清楚关于二分查找的边界问题，不是这里越界，就是那里越界，调试很久也可能A不了，今天，来总结一下关于二分查找

[【LeetCode:34. 在排序数组中查找元素的第一个和最后一个位置】][LeetCode_34.]  
[【牛客网-二分查找】][-]

# 1. 查找特定值 #

对于查找特定值来说，算是二分法的模板题目吧。

// 常规二分
    	public int erFen(int[] nums, int target) {
        
    		int left = 0;
    		int right = nums.length - 1;
    		while (left <= right) {
        
    			int mid = (right - left) / 2 + left;
    			if (nums[mid] == target) {
        
    				return mid;
    			} else if (nums[mid] < target) {
        
    				left = mid + 1;
    			} else if (nums[mid] > target) {
        
    				right = mid - 1;
    			}
    		}
    		return -1;
    	}

# 2. 左侧边界 #

主要来求一个有序数组中，有重复的数字，让你去找重复数字最左边的边界或者第一个大于该数字的

*  还是原来的二分套路
 *  当我们遇到目标值target时，向左进行偏移`right = mid - 1`
 *  最后结束的时候，我们对left的值进行一下判断`left >= nums.length || nums[left] != target`，防止越界

// 左边界二分
    	// 如果当前遇到该值,则往左跑,right = mid - 1;
    	public int leftErFen(int[] nums, int target) {
        
    		int left = 0;
    		int right = nums.length - 1;
    		while (left <= right) {
        
    			int mid = (right - left) / 2 + left;
    			if (nums[mid] == target) {
        
    				right = mid - 1;
    			} else if (nums[mid] < target) {
        
    				left = mid + 1;
    			} else if (nums[mid] > target) {
        
    				right = mid - 1;
    			}
    		}
    		// 如果退出循环了，也就是left = right + 1
    		// 判断下越界了不
    		if (left >= nums.length || nums[left] != target) {
        
    			return -1;
    		}
    		return left;
    	}

# 3. 右侧边界 #

主要来求一个有序数组中，有重复的数字，让你去找重复数字最右边的边界

*  还是原来的二分套路
 *  当我们遇到目标值target时，向右进行偏移`left = mid + 1`
 *  最后结束的时候，我们对right的值进行一下判断`right < 0 || nums[right] != target`，防止越界

// 右界二分
    	// 如果当前遇到该值,则往左跑,right = mid - 1;
    	public int rightErFen(int[] nums, int target) {
        
    		int left = 0;
    		int right = nums.length - 1;
    		while (left <= right) {
        
    			int mid = (right - left) / 2 + left;
    			if (nums[mid] == target) {
        
    				left = mid + 1;
    			} else if (nums[mid] < target) {
        
    				left = mid + 1;
    			} else if (nums[mid] > target) {
        
    				right = mid - 1;
    			}
    		}
    		// 如果退出循环了，也就是left = right + 1
    		// 判断下越界了不
    		if (right < 0 || nums[right] != target) {
        
    			return -1;
    		}
    		return right;
    	}

[LeetCode_34.]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[-]: https://www.nowcoder.com/practice/7bc4a1c7c371425d9faa9d1b511fe193?tpId=188&&tqId=35175&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking