2021-08-03二分查找

#include <stdio.h>
int BinarySearch(int* Nums, int Size, int Left, int Right, int Target);
void test(void);
int main()
{
  test();
  return 0;
}
void test(void) {
  int a[10] = { 3,7,14,17,17,23,27,29,45,67 };
  int find=BinarySearch(a, 10, 0, 9, 23);
  printf("%d\n", find);
   find = BinarySearch(a, 10, 0, 9, 3);
   printf("%d\n", find);
  find = BinarySearch(a, 10, 0, 9, 67);
  printf("%d\n", find);

}
int BinarySearch(int* Nums, int Size, int Left, int Right, int Target) {
  int L = Left; int R= Right;
  while (L<=R)
  {
  int mid = (L + R) / 2;
  if (Nums[mid] == Target)
      return mid;
  else if (Nums[mid] > Target) {
  R=mid-1;
  }
  else {
      L=mid+1;
  }
     }
  if (L > R)return -1;

}

image.png

容易错的地方，R=mid-1,L=mid+1
假设有个数组a[3,5,7]，查找7；第一次L=0,R=2,mid=1,a[1]=5，5<7;
第二次查找，如果让L=mid=1,在[5,7]内查找，那这次的mid=(1+2)/2=1,就会找不到

循环条件为什么是L<=R,二分查找分到最后可能会剩一个元素，这时 L=R;

如果最后那次(L=R)循环还没找到，不管R=mid-1还是L=mid+1（这里的mid=L=R），都会让L>R，返回-1表示没有找到