二分搜索

xiaoxiao2021-02-28  7

      二分搜索,说白了,就是从对一个有序的排列中每次分一半进行查找元素。初学比较难把握的各个值得的范围限制,这属于数学的思维的,不多说,上代码吧。

int binarysearch(int a[],int low,int high,int elem) { if (elem > a[high] || elem < a[low]) { return -1; } int mid = low + (high - low) / 2; if (a[mid] == elem) { return mid; } else if (a[mid] < elem) { binarysearch(a, mid + 1, high, elem); } else if (a[mid] > elem) { binarysearch(a, low, mid-1, elem); } }

上面是递归的,不过一般不这样写,太耗费资源,同时容易导致栈溢出。下面的是普通的写法。 

 

int binarySeearch(int arr[], int low, int high, int key) //这里的arr[]一定需要是有序的,不管是从小到大还是从大到小,low和high是数组的范围,key是查找的关键字 { while (low <= high) //这里low是<=high的,假设现在只有一个元素,也是需要比较的,是吧。 { int mid = low + (high-low) / 2; //这里常写成(low+high)/2,但可能会发生溢出,假如碰到/比较大的数组,high在和low相加后可能会大于int类型的最大值,所以这么写。 if (key == arr[mid]) { return mid; } else if (key < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } }

 

转载请注明原文地址: https://www.6miu.com/read-2249966.html

最新回复(0)