二分查找一＞:在排序数组中查找元素的第一个和最后一个位置

1.题目：  

2.解析:这里不能用传统二分，因为涉及范围，传统二分时间复杂度会降为O(N)，要做些改动。

步骤一：查找区间左端点

细节图：

 

步骤二：查找区间右端点： 

细节图：

 

 

代码： 

public int[] searchRange(int[] nums, int target) {int[] ret = new int[2];ret[0] = ret[1] = -1;if(nums.length == 0) return ret;//二分查找区间左端点int left = 0;int right = nums.length-1;while(left < right){int mid = left+(right-left)/2;if(nums[mid] < target) left = mid+1;else right = mid;}//判断是否有结果if(nums[left] == target){ret[0] = left;}else {return ret;}//二分查找区间右端点left = 0;right = nums.length-1;while(left < right){int mid = left+(right-left+1)/2;if(nums[mid] <= target) left = mid;else right = mid-1;}//判断是否有结果ret[1] = left;return ret;}

 

3.非朴素二分模板：在理解原理基础上