4.1 二分搜索

#include<stdio.h>
//#define MAX_N 1000
const int MAX_N = 1000;
// 二分搜索，找到排序数组中的val出现的位置
int binarySearch(int arr[],int val)
{
    int lo = 0,up = MAX_N - 1;
    while(lo <= up)
    {
        int mid = (lo + up) / 2;
        if(arr[mid] > val) up = mid - 1;
        else if(arr[mid] == val) return mid;
        else lo = mid + 1;
    }
    return -1;
}
// 二分搜索，找到排序数组中的val在数组arr中第一次出现的位置
int binarySearch2(int arr[],int val)
{
    int lo = 0,up = MAX_N - 1;
    while(lo + 1 != up)
    {
        int mid = (lo + up) / 2;
        if(arr[mid] < val) lp = mid;
        else up = mid;
    }
    int p = up ;
    if(p >= n || x[p] != t)
        p = -1;
    return p;
}
int main(void)
{
    int arr[MAX_N];
    int i = 0;
    for(i = 0;i < MAX_N; i++)
        arr[i] = i * 3;
    i = binarySearch(arr,18);
    if(i > -1)
        printf("index = %d , val = %d\n",i,arr[i]);
    return 0;
}