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;
}
