leetcode 二分查找

https://oj.leetcode.com/problems/search-for-a-range/就是一个二分查找，没事练练手

 1 public class Solution {
 2     public int[] searchRange(int[] A, int target) {
 3         int a[]=new int[2];
 4         int ans=bSearch(A,target);
 5         if(ans==-1)
 6         {
 7             a[0]=-1;
 8             a[1]=-1;
 9             return a;
10             
11         }
12         else
13         {
14             int beg=ans;
15             int end=ans;
16             while(beg>=0&&(A[beg]==A[ans]))
17             {
18                 beg--;
19                 
20             }
21             while(end<A.length&&(A[end]==A[ans]))
22             {
23                 end++;
24             }
25             a[0]=beg+1;
26             a[1]=end-1;
27             return a;
28             
29         }
30         
31         
32         
33     }
34     public int bSearch(int[] A,int target)
35     {
36         int low=0;
37         int high=A.length-1;
38         while(low<=high)
39         {
40             int mid =(low+high)/2;
41             if(A[mid]==target)
42             {
43                 return mid;
44                 
45             }
46             else if(A[mid]>target)
47             {
48                 
49                
50                 high=mid-1;
51                 
52             }
53             else
54             {
55                 low=mid+1;
56             }
57             
58             
59             
60         }
61         
62         return -1;
63     }
64     
65     
66     
67 }

2.另外一种二分查找 beg=0 end=len; end指向的是最后一个元素的后面，

 1 public class Solution {
 2     public int[] searchRange(int[] A, int target) {
 3         int a[]=new int[2];
 4         int ans=bSearch(A,target);
 5         if(ans==-1)
 6         {
 7             a[0]=-1;
 8             a[1]=-1;
 9             return a;
10             
11         }
12         else
13         {
14             int beg=ans;
15             int end=ans;
16             while(beg>=0&&(A[beg]==A[ans]))
17             {
18                 beg--;
19                 
20             }
21             while(end<A.length&&(A[end]==A[ans]))
22             {
23                 end++;
24             }
25             a[0]=beg+1;
26             a[1]=end-1;
27             return a;
28             
29         }
30         
31         
32         
33     }
34     public int bSearch(int[] A,int target)
35     {
36         int low=0;
37         int high=A.length;
38         while(low<high)  //low<high不能等于
39         {
40             int mid =(low+high)/2;
41             if(A[mid]==target)
42             {
43                 return mid;
44                 
45             }
46             else if(A[mid]>target)
47             {
48                 
49                
50                 high=mid;
51                 
52             }
53             else
54             {
55                 low=mid+1;
56             }
57             
58             
59             
60         }
61         
62         return -1;
63     }
64     
65     
66     
67 }

3.第一种方法的递归方式

 1 public class Solution {
 2     public int[] searchRange(int[] A, int target) {
 3         int a[]=new int[2];
 4         int ans=bSearch(A,target,0,A.length);
 5         if(ans==-1)
 6         {
 7             a[0]=-1;
 8             a[1]=-1;
 9             return a;
10             
11         }
12         else
13         {
14             int beg=ans;
15             int end=ans;
16             while(beg>=0&&(A[beg]==A[ans]))
17             {
18                 beg--;
19                 
20             }
21             while(end<A.length&&(A[end]==A[ans]))
22             {
23                 end++;
24             }
25             a[0]=beg+1;
26             a[1]=end-1;
27             return a;
28             
29         }
30         
31         
32         
33     }
34     public int bSearch(int[] A,int target,int low,int high)
35     {
36        
37         while(low<high)
38         {
39             int mid =(low+high)/2;
40             if(A[mid]==target)
41             {
42                 return mid;
43                 
44             }
45             else if(A[mid]>target)
46             {
47                 
48                
49                 bSearch(A,target,low,mid);
50                 
51             }
52             else
53             {
54                 bSearch(A,target,mid,high);
55             }
56             
57             
58             
59         }
60         
61         return -1;
62     }
63     
64     
65     
66 }