04.二分查找
一、题目思路
1、先排序数组两段各各取一个索引值:start=0、end=n-1
2、当start <= end时都需要判断
3、mid = start + ((end-start)>>1) 防止 start + end 溢出
4、arr[mid] > num, end = mid - 1;
5、arr[mid] < num, start = mid + 1;
6、如不存在,插入时选 end + 1位置插入
二、代码实现
#include <stdio.h>
#include <stdlib.h>
int binary_search(int *arr, int size, int num)
{
if (!size)
return -1;
int start = 0;
int end = size - 1;
while (start <= end) {
int mid = start + ((end-start)>>1);
if (arr[mid] > num)
{
printf("end = mid %d\n", mid);
end = mid - 1;
} else if (arr[mid] < num)
{
printf("start = mid %d\n", mid);
start = mid + 1;
} else {
printf("find mid\n");
return mid;
}
}
printf("not find, insert index:%d\n", end + 1);
return -1;
}
void bubble_sort(int *arr, int size)
{
int i;
int j;
for (i = 0; i < size - 1; i++) {
for (j = 0; j < size - 1 - i; j++){
if (arr[j] > arr[j+1]) {
int tmp;
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
return;
}
void show(int *arr, int size)
{
for (int i = 0; i < size; i++) {
if (i == size-1)
printf("%d\n", arr[i]);
else
printf("%d,", arr[i]);
}
return;
}
int main(int argc, char *argv[])
{
int num[] = {33,5,18,1,1,2,9};
int size = sizeof(num)/sizeof(int);
int num_search = atoi(argv[1]);
bubble_sort(num, size);
show(num, size);
int ret = binary_search(num, size, num_search);
printf("%d\n", ret);
return 0;
}
原文地址:https://blog.csdn.net/sinat_38201303/article/details/145161604
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!