1、迭代实现二分查找
int b_s1(int t[], int i, int j, int s)
{
if(s < t[i] || s > t[j])
{
return -1;
}
while(1)
{
if(i > j)
{
return -1;
}
int m = (i + j)/2;
if(t[m] == s)
{
return m;
}
else if(t[m] < s)
{
i = m + 1;
}
else
{
j = m - 1;
}
}
}
2、递归实现二分查找
int b_s(int t[], int i, int j, int s)
{
if(i > j)
{
return -1;
}
if(s < t[i] || s > t[j])
{
return -1;
}
int m = (i + j)/2;
if(t[m] == s)
{
return m;
}
else if(t[m] < s)
{
i = m + 1;
}
else
{
j = m - 1;
}
return b_s(t, i, j, s);
}
3、习题之一，二分查找第一个出现的查找数据
int b_s2(int t[], int i, int j, int s)
{
int sch = -1;
if(s < t[i] || s > t[j])
{
return -1;
}
while(1)
{
if(i > j)
{
return sch;
}
int m = (i + j)/2;
if(t[m] == s)
{
sch = m;
j = m - 1;
}
else if(t[m] < s)
{
i = m + 1;
}
else
{
j = m - 1;
}
}
}
4、完整程序，含测试部分
int b_s(int t[], int i, int j, int s)
{
if(i > j)
{
return -1;
}
if(s < t[i] || s > t[j])
{
return -1;
}
int m = (i + j)/2;
if(t[m] == s)
{
return m;
}
else if(t[m] < s)
{
i = m + 1;
}
else
{
j = m - 1;
}
return b_s(t, i, j, s);
}
int b_s1(int t[], int i, int j, int s)
{
if(s < t[i] || s > t[j])
{
return -1;
}
while(1)
{
if(i > j)
{
return -1;
}
int m = (i + j)/2;
if(t[m] == s)
{
return m;
}
else if(t[m] < s)
{
i = m + 1;
}
else
{
j = m - 1;
}
}
}
int b_s2(int t[], int i, int j, int s)
{
int sch = -1;
if(s < t[i] || s > t[j])
{
return -1;
}
while(1)
{
if(i > j)
{
return sch;
}
int m = (i + j)/2;
if(t[m] == s)
{
sch = m;
j = m - 1;
}
else if(t[m] < s)
{
i = m + 1;
}
else
{
j = m - 1;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int t[10] ;
for(int i = 0; i < 10; i++)
{
t[i] = i + 1;
}
int index = b_s(t, 0, 9, 5);
index = b_s(t, 0, 9, 10);
index = b_s(t, 0, 9, 10000);
index = b_s(t, 0, 9, 0);
index = b_s(t, 0, 9, -1);
index = b_s1(t, 0, 9, 5);
index = b_s1(t, 0, 9, 10);
index = b_s1(t, 0, 9, 10000);
index = b_s1(t, 0, 9, 0);
index = b_s1(t, 0, 9, -1);
index = b_s2(t, 0, 9, 5);
index = b_s2(t, 0, 9, 10);
index = b_s2(t, 0, 9, 10000);
index = b_s2(t, 0, 9, 0);
index = b_s2(t, 0, 9, -1);
t[2] = 4;
index = b_s2(t, 0, 9, 4);
for(int i = 1; i < 9; i++)
{
t[i] = 5;
}
index = b_s2(t, 0, 9, 5);
return 0;
}
5、第七题
给定一个满足0<= x <= 1的点(x, y)，查找包围这个点的两个线段，前提条件就是0 到 1之间，所有线段不相交，y值递增。
解题分支：
递增可以使用二分查找，直接找最后一个比指定点大的线段，这个线卡要么在最靠近这个点之上，要么这个点就在上面。找到后，索引－1，自然就是最靠近的下面的那个线段了。
#include<stdio.h>
typedef struct point
{
int x;
int y;
}POINT;
/*the up_index must be initialised as -1, or something else below the 0*/
void get_approximate_line_up_index(POINT *p,
int low,
int high,
double d_x,
double d_y,
int &up_index
)
{
int m = 0;
if(p[high].x * d_x + p[high].y < d_y)
{
return ;
}
if(p[low].x * d_x + p[low].y > d_y)
{
return ;
}
while(1)
{
if(low > high)
{
return;
}
m = (low + high) / 2;
if(p[m].x * d_x + p[m].y < d_y)
{
low = m + 1;
}
else if(p[m].x * d_x + p[m].y > d_y)
{
up_index = m;
high = m - 1;
}
else
{
up_index = m;
return ;
}
}
}
void print_line_pair(int low, int high, int index)
{
int m_l = 0;
int m_h = 0;
if(low >= high)
{
printf("invalid input\n");
return;
}
if(index < low || index > high)
{
printf("no match pair\n");
return;
}
if(index == low)
{
m_l = low;
m_h = high;
}
else
{
m_l = index - 1;
m_h = index;
}
printf("macth pair is (low = %d, high = %d)\n", m_l, m_h);
}
int main()
{
POINT p[] = {
{ 1, 2},
{ 2, 2},
{ 3, 2},
{ 4, 2},
{ 5, 2},
{ 6, 2},
{ 7, 2},
{ 8, 2},
{ 9, 2},
{ 10, 2},
{ 11, 2},
};
int p_size = sizeof p/sizeof p[0];
/*find the (0.5, 3.1)*/
double x = 0.5;
int up_index = -1;
for(int index = 0; index < p_size; index++)
{
printf("(x, y) is (%lf, %lf) \n", x, p[index].x * x + p[index].y);
}
printf("\n\n");
get_approximate_line_up_index(p, 0, p_size - 1, x, 3.1, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 4.0, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 4.1, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 4.5, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 4.6, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 5.1, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 5.6, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 6.1, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 6.6, up_index);
print_line_pair(0, p_size - 1, up_index);
up_index = -1;
get_approximate_line_up_index(p, 0, p_size - 1, x, 7.1, up_index);
print_line_pair(0, p_size - 1, up_index);
}