[leetcode]Search for a Range

（本博文作废，算法太挫，新博文将代码压缩至一半以下，可读性也更好）

新博文地址：[leetcode]Search for a Range

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

 要求时间复杂度为O(log n)，再加上排序的条件，毫无疑问需要二分查找。return[-1,-1]的判断很容易，不再啰嗦。当找到target之后，需要将数组a分为两段，并在前半段寻找target的前驱，在后半段寻找target的后驱。毫无疑问，还得用折半查找。

这个程序目前在leetcode做的100+道题中，代码最长的一道，时间复杂度O(log n)，空间复杂度O(1)，效率已经不需要优化了，只不过代码长的我看着都恶心，不过好在都是重复代码，不存在可读性的问题。我是有多懒得动脑子啊。。。。o(╯□╰)o

public int[] searchRange(int[] A, int target) {
        int index = fillIndex(A,target);
        if(index == -1){
        	return new int[]{-1,-1};
        }
        int begin = findBegin(A,0,index,target);
        int end = findEnd(A,index,A.length - 1,target);
        return new int[]{begin,end};
   }

   private int fillIndex(int[] a,int target){//找到target，找不到则返回-1
   	int begin = 0; 
   	int end = a.length - 1;
   	while(begin <= end){
   		int mid = (begin + end) >> 1;
   		if(a[mid] == target){
   			return mid;
   		}else if(a[mid] > target){
   			end = mid - 1;
   		}else{
   			begin = mid + 1;
   		}
   	}
   	return -1;
   }

   private int findBegin(int[] a,int begin ,int end,int target){//在前半段找target的前驱
		while(begin <= end){
			int mid = (begin + end)>>1;
			if(a[mid] == target){
				end = mid - 1;
				if(end < begin ){
	   				break;
	   			}
				if(a[end] < target){
					return mid;
				}
			}else if(a[mid] < target){
				begin = mid + 1;
				if(begin == a.length){
	   				break;
	   			}
				if(a[begin] == target){
					return begin;
				}
			}
		} 
		return 0;
   }

   private int findEnd(int[] a,int begin,int end,int target){//在后半段找target的后驱
   	while(begin <= end){
   		int mid = (begin + end)>>1;
   		if(a[mid] == target){
   			begin = mid + 1;
   			if(begin == a.length){
   				break;
   			}
   			if(a[begin] > target){
   				return mid;
   			} 
   		}else if(a[mid] > target){
   			end = mid - 1;
   			if(end < begin ){
   				break;
   			}
   			if(a[end] == target){
   				return end;
   			}
   		}
   	}
   	return a.length - 1;
   }