二分查找介绍

二分查找也称折半查找（Binary Search），是一种效率较高的查找方法。

二分查找适用场景

有序不重复的数组中元素的查找。

代码实现

int findNumIndex(int *arr,int len,int n){int end = len; int start = 0;//越界 if(n > *(arr+len-1) || n < *(arr)){return -1;}while(1){int midIdx = (end + start) / 2;if(start == midIdx && *(arr+midIdx) != n){return -1;}if(*(arr+midIdx) == n){return midIdx;}else if(*(arr+midIdx) > n){end = midIdx;}else{start = midIdx;}}}

实现过程分析

首先，假设数组中的元素是按升序排列的，将最中间的数字和要搜索的数字进行比较，如果两者相等，则搜索成功； 否则，从中间数字位置将数组分为两个子数组，前数组和后数组，如果中间数字大于搜索数字，则进一步查找前数组中的元素，否则在后一个数组中进行查找。 重复上述过程，直到找到满足条件的数字，则搜索成功，或者直到子表所有的数字查找完毕还没有找到该数字，此时搜索不成功。