二分搜索算法 2021-03-05

1. 
//写法<一>
2. #include <iostream>
3. using namespace std;
4. int nums[10]={1,3,3,3,4};
5. int binarySearch1(int nums[],int target){//搜索区间[left,right] 寻找一个数 
6.  int left=0;
7.  int right=4;//注意 
8.  while(left<=right){
9.    int mid=left+(right-left)/2;
10.     if(nums[mid]==target)return mid;
11.     else if(nums[mid]<target)left=mid+1;
12.     else if(nums[mid]>target)right=mid-1;
13.   }
14.   return -1;//注意
15. }
16. int binarySearch2(int nums[],int target){//搜索区间[left,right) 寻找左侧边界 
17.   int left=0;
18.   int right=5;//注意 
19.   while(left<right){
20.     int mid=left+(right-left)/2;
21.     if(nums[mid]==target)right=mid;
22.     else if(nums[mid]<target)left=mid+1;
23.     else if(nums[mid]>target)right=mid;
24.   }
25.   return left;//注意
26. }
27. int binarySearch3(int nums[],int target){//搜索区间[left,right) 寻找右侧边界 
28.   int left=0;
29.   int right=5;//注意 
30.   while(left<right){
31.     int mid=left+(right-left)/2;
32.     if(nums[mid]==target)left=mid+1;
33.     else if(nums[mid]<target)left=mid+1;
34.     else if(nums[mid]>target)right=mid;
35.   }
36.   return left-1;//注意
37. }
38. int main(int argc, char *argv[])
39. {
40.   cout<<binarySearch1(nums,3)<<endl;
41.   cout<<binarySearch2(nums,3)<<endl;
42.   cout<<binarySearch3(nums,3)<<endl;
43.   return 0;
44. }

1. //写法<二> 
2. #include <iostream>
3. using namespace std;
4. int nums[10]={1,3,3,3,4};
5. int binarySearch1(int nums[],int target){//搜索区间[left,right] 寻找一个数 
6.  int left=0;
7.  int right=4;//注意 length-1 
8.  while(left<=right){
9.    int mid=left+(right-left)/2;
10.     if(nums[mid]==target)return mid;//注意
11.     else if(nums[mid]<target)left=mid+1;
12.     else if(nums[mid]>target)right=mid-1;
13.   }
14.   return -1;
15. }
16. int binarySearch2(int nums[],int target){//搜索区间[left,right) 寻找左侧边界 
17.   int left=0;
18.   int right=4;//注意 length-1 
19.   while(left<=right){
20.     int mid=left+(right-left)/2;
21.     if(nums[mid]==target)right=mid-1;//注意
22.     else if(nums[mid]<target)left=mid+1;
23.     else if(nums[mid]>target)right=mid-1;
24.   }
25.   if(left>=4||nums[left]!=target)//检查left越界情况 
26.     return -1;
27.   return left;
28. }
29. int binarySearch3(int nums[],int target){//搜索区间[left,right) 寻找右侧边界 
30.   int left=0;
31.   int right=4;//注意 length-1 
32.   while(left<=right){
33.     int mid=left+(right-left)/2;
34.     if(nums[mid]==target)left=mid+1;//注意
35.     else if(nums[mid]<target)left=mid+1;
36.     else if(nums[mid]>target)right=mid-1;
37.   }
38.   if(right<0||nums[right]!=target)//检查right越界情况 
39.     return -1;
40.   return right;
41. }
42. int main(int argc, char *argv[])
43. {
44.   cout<<binarySearch1(nums,3)<<endl;
45.   cout<<binarySearch2(nums,3)<<endl;
46.   cout<<binarySearch3(nums,3)<<endl;
47.   return 0;
48. }