34. 在排序数组中查找元素的第一个和最后一个位置

#34. 在排序数组中查找元素的第一个和最后一个位置

题目描述

解题思路
这道题乍一看很简单啊，居然还是中等难度，虽然题目要求时间复杂度是O(log n)，但是用普通O(n)的也过了。其实真正要考察的是二分查找的思想
1、二分查找思想
写了一个不太正宗的二分查找，按道理时间复杂度应该还是O(n)，但是提交上去效果还不错，不知道咋回事。

public int[] searchRange(int[] nums, int target) {        
	int p = 0,q = nums.length - 1;        
	while(p <= q) {            	
		int mid = p + (q-p)/2;            
		if(nums[mid] < target) {                
			p = mid + 1;            
		}            
		else if(nums[mid] > target) {                
			q = mid - 1;            
		}            
		else if(nums[mid] == target) {  //找到目标           
			if(nums[p] < target)                    
				p++;                
			if(nums[q] > target)                    
				q--;                
			else if (nums[p] == nums[q]) {                   
				return new int[]{p,q};                
				}            
			}        
		}        
		return new int[]{-1,-1};    
	}

正宗的二分查找，找左右边界的时候都应该用二分查找。找左边界从右边收缩，找右边界从左边收缩。有个题解写的超级好，链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/

public int[] searchRange(int[] nums, int target) {        
	int p = left_bound(nums,target);        
	int q = right_bound(nums,target);        
	return new int[]{p,q};    
}    
int left_bound(int[] nums, int target) {        
	int left = 0, right = nums.length - 1;        
	while (left <= right) {            
		int mid = left + (right - left) / 2;            
		if (nums[mid] < target) {                
			left = mid + 1;            
		} 
		else if (nums[mid] > target) {                
			right = mid - 1;            
		} 
		else if (nums[mid] == target) {                
			// 别返回，收缩左侧边界                
			right = mid - 1;            
		}        
	}        
	// 最后要检查 left 越界的情况        
	if (left >= nums.length || nums[left] != target)            
		return -1;        
	return left;    
}

    int right_bound(int[] nums, int target) {       	
    	int left = 0, right = nums.length - 1;        
    	while (left <= right) {            
    		int mid = left + (right - left) / 2;            
    		if (nums[mid] < target) {                
    			left = mid + 1;            
    		} 
    		else if (nums[mid] > target) {                
    			right = mid - 1;            
    		} 
    		else if (nums[mid] == target) {                
    		// 别返回，收缩右侧边界                
    			left = mid + 1;            
    		}        
    	}        
    	// 最后要检查 right 越界的情况        
    	if (right < 0 || nums[right] != target)            
    		return -1;        
    	return right;    
    }

2、普通遍历
这个没啥技术含量，很简单

public static int[] searchRange(int[] nums, int target) {
  	int p = 0,q = nums.length - 1;
  	while(p < q) {
   		if(nums[p] < target)
    			p++;
   		if(nums[q] > target)
    			q--;
   		if(nums[p] == target && nums[q] == target)
    			break;
  	}
  	if(p <= q && nums[p] == target)
   		return new int[]{p,q};
  	else
   		return new int[]{-1,-1};
    }

运行结果：