二分查找详解

绝地灬酷狼 2022-09-26 03:59 66阅读 0赞

**基本概念：**

在计算机科学中，二分搜索(binary search)，也称折半搜索(half-interval search)，**是一种在有序数组中查找某一特定元素的搜索算法**。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。  
  
  
**时间复杂度：**  
折半搜索每次把搜索区域减少一半，时间复杂度为O(logn)

**简单例子：**

#include <stdio.h>
    
    /* 返回找到的下标 */
    int binary_search(const int arr[], int start, int end, int key)
    {
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2; /* 直接相加再求平均可能会溢出 */
            if (arr[mid] < key)
                start = mid + 1;
            else if (arr[mid] > key)
                end = mid - 1;
            else
                return mid;
        }
        return -1;
    }
    
    int main()
    {
        int arr[] = {1, 3, 5, 7, 9, 10, 12, 34, 77, 87};
        int size = sizeof(arr) / sizeof(int);
        int start = 0;
    
        //find 5
        int key = 5;
        int index = binary_search(arr, start, size-1, key);
    
        if (index == -1) {
            printf("not found %d\n", key);
        } else {
            printf("found %d\n", key);
        }
    
        key = 88;
        index = binary_search(arr, start, size-1, key);
        if (index == -1) {
            printf("not found %d\n", key);
        }
    
        return 0;
    }

**编译运行：**

![SouthEast][]

原文出自：[http://blog.csdn.net/daiyudong2020/article/details/52601340][http_blog.csdn.net_daiyudong2020_article_details_52601340]

End;

[SouthEast]: /images/20220717/dda984780a094eb59c2b8ade101b7621.png
[http_blog.csdn.net_daiyudong2020_article_details_52601340]: http://blog.csdn.net/daiyudong2020/article/details/52601340