首页 > 其他 > 详细

二分法

时间:2015-10-19 20:56:29      阅读:162      评论:0      收藏:0      [点我收藏+]

描述
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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!