使用C、Java实现二分查找

二分法非常容易理解，它的核心思想是折半查找，直到查到目标元素（也可能找不到）。使用二分法有一个前提条件：元素必须是已经排好序的。

二分法和一般查找的算法时间复杂度对比：

• 一般查找 O(n)
• 二分法 O(logn)

二分查找比一般查找快的多，当元素个数n为1024时，一般查找需要执行1024次，而二分法只需要执行10次。当元素个数越多，后者就比前者更快的多。

实现二分法也比较容易，关键有两点：

• 折半查找
• 什么时候跳出循环

什么时候跳出循环结束查找？当然，如果找到了目标元素，那么肯定会结束循环，但如果一直没有找到呢？是low比heig大的情况结束循环，还是low大于或等于heig的情况下结束循环。

我们考虑一种特殊的情况，如果元素只有一个，那么low等于heig，这么情况下肯定需要查找一次才能知道目标元素在不在。所以可以得出，当low>heig的情况下，结束循环。

C语言实现

#include<stdio.h>

int main (void) {
    int nums[] = {1,3,5,34,56,453,2321,32354};

    int n = binsearch(nums, 8, 56);
    printf("%d\n", n);
}

int binsearch (int nums[], int len, int item)
{
    int left = 0;
    int right = len -1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;

        if (nums[mid] > item) {
            right = mid -1;
        } else if (nums[mid] < item) {
            left = mid + 1;
        } else {
            return mid;
        }
    }

    return -1;
}

Java实现

public class Binsearch {
    public static void main(String[] args) {
        int[] nums = {1,3,4,5,6,8,9,10,12,14,24,45,67,87,99,100};

        int[] items = {3,8,10, 14, 45, 67, 89, 101};
        for (int item:items) {
            int index = search(nums, item, nums.length);

            if ( index > -1) {
                System.out.println(item + "-" + index);
            } else {
                System.out.println("not found");
            }
        }

    }

    private static int search (int[] nums, int item, int len)
    {
        int low = 0;
        int heig = len -1;
        int mid;

        while (low <= heig) {
            mid = (low + heig) / 2;

            if (item == nums[mid]) {
                return mid;
            } else if (item > nums[mid]) {
                low = mid + 1;
            } else {
                heig = mid - 1;
            }
        }

        return -1;
    }
}