Binary Search

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。

• 算法要求：

• 必须采用顺序存储结构
• 必须按关键字大小有序排列

实现：

int bianrySearch(int nums[], int size, int val)  
{  
    int start = 0;  
    int end = size - 1;  
    int index = -1;  
    while(start <= end)  
    {  
        index = (start + end) / 2;  
        if(nums[index] == val)  return index;
        else if(nums[index] < val) start = index + 1; 
        else  end = index - 1; 
    }  
    return -1;  //not found
}