二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

查找过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

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

递归实现

#include<iostream>
using namespace std;
int a[100]={1,2,3,5,12,12,12,15,29,55};//数组中的数（由小到大）
int k;//要找的数字
int found(int x,int y)
{
    int m=x+(y-x)/2;
    if(x>y)//查找完毕没有找到答案，返回-1
        return -1;
    else
    {
        if(a[m]==k)
            return m;//找到后返回位置.
        else if(a[m]>k)
            return found(x,m-1);//找左边
         else
            return found(m+1,y);//找右边
    }
}
int main()
    {
        cin>>k;
        cout<<found(0,9);
        return 0;
    }

循环实现

public static int Method(int[] nums, int low, int high, int target)
        {
            while (low <= high)
            {
                int middle = (low + high) / 2;
                if (target == nums[middle])
                {
                    return middle;
                }
                else if (target > nums[middle])
                {
                    low = middle + 1;
                }
                else if (target < nums[middle])
                {
                    high = middle - 1;
                }
            }
            return -1;
        }