自学内容网 自学内容网

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)!