Binary Search--二分查找

　　采用二分法查找时，数据需是排好序的。 基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段 中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

　　二分法查找在针对大量有序排列的情况下发挥出很优越的效率，其时间复杂度O(lgN)。

　　

　　代码：

1 /* 2 Author:Mengmeng 3 Time:2016-6-27 23:33:49 4 Description: 5     采用二分法查找时，数据需是排好序的。  6     基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较， 7     如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段 中查找； 8     若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。 9 */10 #include 
     
      11 using namespace std;12 13 14 int BinarySearch(int data[],int min,int max,int dest,bool UpOrDown)15 {16     int mid = 0;17     if (min > max)//递归结束条件18     {19         cout << "找不到" << dest << "!"<
      
       > dest;57     cout <<"----------------------------------------"<< endl;58     int index = BinarySearch(data1, 0, len - 1, dest,true);59 #endif60 #if 161     cout << "请参照下列数字：" << endl;62     cout << "{
    ";63     int len = sizeof(data2) / sizeof(int);64     for (int i = 0; i < len; i++)65         cout << data2[i] << " ";66     cout << "}" << endl;67     cout << "输入你要查找的目标：" << endl;68     int dest;69     cin >> dest;70     cout << "----------------------------------------" << endl;71     int index = BinarySearch(data2, 0, len - 1, dest, false);72 #endif73     if (index!=-1)74         cout << dest << "在数组中的位置为第" << index << "个" << endl;75     return 0;76 77 }
      
     

 

 

　　运行结果：

　　（1）升序的情况：

　　　　

　　

　　（2）降序的情况：