博客

二分查找法，也称折半查找；



折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列；


因为这个数组是排好序的，所以将当前的比较区间的中间值与目标元素比较，目标元素比中间值大，则说明目标元素可能在数组的右半部分，否则在左半部分，一次递归，知道找到这个目标元素为止；

判断没找到，只要left>right就说明没有找到，因为当if条件不满足时，无法确实mid左右两边的left和right，不满足条件return返回-1，说明没有找到。

#include<stdio.h>
int BinarySearch0(int* arr, int len, int left, int right,int value) 
{
 //1 退出条件
 if (left > right) 
 {
  return -1; // 不存在该数据
 }
 int midIndex = ((right-left)>>1) + left;//(left+right)>>1
 if (arr[midIndex] == value) 
 {
  return midIndex;
 }
 //2. 自己调自己 （问题规模缩小）
 if (arr[midIndex] > value) 
 {
  return BinarySearch0(arr,len,left,midIndex-1,value);
 }
 else 
 {  //arr[midIndex] < value
  return BinarySearch0(arr,len, midIndex+1, right, value);
 }
}
int BinarySearch(int* arr, int len,int value) 
{
 int left = 0, right = len - 1;  //左边界，右边界下标  范围
 int index = BinarySearch0(arr, len, left, right,value);
 return index;
}

int main() 
{
 int arr[] = {1,2,3,4,6};
 int n;
 printf("请输入需要查找的元素(若弹出-1则说明没有找到该数)\n"); 
 scanf("%d",&n) ;
 printf("在下标%d处", BinarySearch(arr, 5, n));
 return 0;
}