//
//  main.c
//  05折半查找到 代码实现
//
//  Created by apple on 15-1-5.
//  Copyright (c) 2015年 itcast. All rights reserved.
//

#include <stdio.h>
/**
* 使用折半查找来查找一个数
*
*  @param arr 数组
*  @param len 数组的长度
*
*  @return 要查找的数的位置，如果查不到返回 -1
*/
int searchItem(int arr[],int len,int key)
{
   
    //先要定义变量
    int low,high=len-1,mid;
   
    //循环
    while(low<=high)
    {
        
        
        //计算 mid 的位置
        mid = (low+high)/2;
        
        //判断 key a[mid],右半区查找
        if(key>arr[mid])
        {
            //key > a[mid]  low = mid +1
            low = mid +1;
        }
        else if(key<arr[mid])
        {
            //key < a[mid] high = mid -1
            high = mid-1;
        }
        else
        {
            //key == a[mid]  return mid
            return mid;
        }
        
        
    }
    return -1;

}
int insertItemLoc(int arr[],int len,int key)
{
    //先要定义变量
    int low=0,high=len-1,mid;
    //循环
    while(low<=high)
    {
        //计算mid的位置
        mid = (low+high)/2;
        if(key>arr[mid])
        {
            //判断key a[mid]右半区查找
            low = mid+1;
        }
        else if(key<arr[mid])
        {
            high = mid-1;
        }
        else
        {
            return mid +1;//插入数的时候插入的位置
        }
    }
    return low;//如果插入的数数组里没有择该插入的位置
}

int main(int argc, const char * argv[])
{
   
   
    int a[]={3,4,12,20,21,23,28,45,67,100};
    //查找20 key=20;
   
   
  // int loc = searchItem(a,10,20);
    int loc = insertItemLoc(a,10,20);
    printf("%d\n",loc);
}

折半查找！