二分查找算法

 1 #include<stdio.h>
 2 /* 线性查找 */ 平均时间复杂度 O（n）
 3 size_t line_find (int data[],size_t size,int key){
 4     size_t i;
 5     for (i=0;i<size;++i)
 6     if(data[i] == key)
 7         return i;
 8     return -1;
 9 }
10 /* 二分查找 */ 平均时间复杂度 O（log n）
11 size_t half_find (int data[],size_t size,int key){
12     int left = 0;
13     int right = size-1;
14     while(left <= right){
15     int mid = (left+right)/2;
16     if(key < data[mid])
17         right = mid-1;
18     else
19         if(data[mid] < key)
20         left = mid+1;
21         else
22         return mid;
23     }
24     return -1;
25 }
26 int main (){
27     int data[] = {13,44,45,46,60};
28     size_t size = sizeof(data)/sizeof(data[0]);
29     size_t i = half_find(data,size,60);
30     if(i==-1)
31     printf("没找到
");
32     else
33     printf("找到了%d
",i);
34     return 0;
35 }

特殊条件的二分查找：

Q：一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}

是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

A：任意将这个数组从中间分开，分成两个数组，则至少有一个数组单调递减，另一个数组则可以由递减数组左移若干位得到，所以我们在二分之后确定界限的时候必须考虑所有情况，即需要查找的数组在哪一个分区里。

首先我们需要判断哪一个分区是单调递减的分区，这可以通过比较arr[l]和arr[mid]来得到，如果是大于等于，则左分区是单调递减，否则是右分区；再通过判断要查找的值是否夹在递减分区中间来最终确定选择哪一个分区。

 1 #include <iostream>
 2 using namespace std;
 3  
 4 int FindData(int* arr,int value,int l,int r)
 5 {
 6     while(l<=r)
 7     {
 8         int mid=(l+r)/2;
 9         if(arr[mid]==value)
10             return mid;
11         else
12         {
13             if(arr[l]>=arr[mid])
14             {
15                 if(value>arr[mid] && value<=arr[l])
16                     r=mid-1;
17                 else
18                     l=mid+1;
19             }
20             else
21             {
22                 if(value<arr[mid] && value>=arr[r])
23                     l=mid+1;
24                 else
25                     r=mid-1;
26             }
27         }
28     }
29     return -1;
30 }
31  
32 int main()
33 {
34     int arr[]={4,3,2,1,6,5};
35     int n;
36     cin >>n;
37     cout <<FindData(arr,n,0,5)<<endl;
38     return 0;
39 }