折半查找
折半查找
折半查找:在一个有序数组中找一个数,找到返回下标,找不到返回-1;
个人思路:
1.首先,我们先让begin和end指向第一个和最后一个数,然后mid指向中间的数,假设我们找数字6;
2.然后将mid所指的数与我们所找的数相比较,如果大于mid,那么将begin指向mid位置的右侧,同时令 mid 重新指向 begin 和 end的中间位置;反之,则将end指向mid的左侧,同时令 mid 重新指向 begin 和 end的中间位置;如果相等,则返回mid;找不到,返回-1;
下面我们来看看代码:
#include <stdio.h>
#include <stdlib.h>
int search(int* a, int x, int size)
{
int begin = 0;
int end = size - 1;
int mid = 0;
while (begin <= end)
{
mid = (begin + end) / 2;
if (x == a[mid])
return mid;
else if (x > a[mid])
begin = mid+1;
else
end = mid-1;
}
return -1;
}
int main()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int sz = sizeof(array) / sizeof(int);
int index = search(array, 1, sz);
printf("%d", index);
system("pause");
return 0;
}