描述
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].
1 #include <iostream> 2 3 int binarySeachch(int A[],int length,int target) 4 { 5 int head =0; 6 int tail = length-1; 7 8 while(head <= tail) 9 { 10 int cur = (head+tail)/2; 11 12 if(target > A[cur]) 13 { 14 head = cur+1; 15 } 16 else if(target < A[cur]) 17 { 18 tail = cur-1; 19 } 20 else 21 return cur; 22 } 23 return -1; 24 } 25 26 int lowerBound(int A[],int length,int target) 27 { 28 int head = 0; 29 int tail = length-1; 30 int cur = (head+tail)/2; 31 while(head < tail) 32 { 33 if(A[cur] >= target) 34 { 35 tail=cur; 36 } 37 else 38 { 39 head = cur + 1; 40 } 41 cur = (head+tail)/2; //notice 42 } 43 if(A[cur]>=target) 44 return cur; 45 else 46 return -1; 47 } 48 49 int upperBound(int A[],int length,int target) 50 { 51 int head = 0; 52 int tail= length-1; 53 int cur = (head+tail)/2; 54 55 while(head < tail) 56 { 57 if(A[cur] <= target) 58 { 59 head = cur+1; 60 } 61 else if(A[cur] > target) 62 { 63 tail = cur; 64 } 65 cur = (head+tail)/2; 66 } 67 if(A[cur] > target) 68 return cur; 69 else 70 return -1; 71 } 72 73 74 int main() 75 { 76 int A[] = {5,7,7,8,8,9}; 77 78 std::cout << lowerBound(A, 6, 8)<< std::endl; 79 std::cout << upperBound(A, 6, 8) << std::endl; 80 81 return 0; 82 }
原文:http://www.cnblogs.com/wxquare/p/4892916.html