二分查找:在一组数中找到指定的数
//1. 存储在数组中(如果是链表则无法使用二分查找) //2. 有序的排列 (递增或递减,或重复数都无影响)
递归法:
//param:有序数组,检索开始为止,结束为止,要查找的数字 //return:返回目标数字所在为止,没有找到返回-1 int binSearch (int arr[], int low, int high, int key) { if (low <= high) { int mid = (low + high)/2; if (key == arr[mid]) return mid; else if (key < arr[mid]) return binSearch(arr,low,mid-1,key); else if (key > arr[mid]) return binSearch(arr,mid+1,high,key); } else return -1; }
循环查找:
//param:有序数组,数组大小,需要查找的数 //return:查找的数所在位置,找不到返回-1 int binSearch (int *arr, int size, int key) { if (arr == NULL || size == 0) return -1; int low = 0, high = size -1, mid = 0; while (low<=high) { mid = (low+high)/2; if (arr[mid] < key) low = mid + 1; else if (arr[mid] > key) high = mid - 1; else return mid; } return -1; }
参考原文:https://blog.csdn.net/idream68/article/details/89352653