二分法的四个简单应用

一.寻找有序数组中的元素

--寻找一个有序数组中的某个元素，并输出其下标

//寻找有序数组中的某个元素
#include<stdio.h>
int main()
{
  int arr[] = { -1,2,4,5,7,8,9,11 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  int left = 0, n;
  int right = sz - 1;
  scanf("%d", &n);
  while (left<=right)
  {
    int mid = left + (right - left) / 2;
    if (arr[mid]>n)
    {
      right = mid - 1;
    }
    else if (arr[mid]<n)
    {
      left = mid + 1;
    }
    else
    {
      printf("找到了，该元素下标为%d\n", mid);
      break;
    }
  }
  if (left>right)
  {
    printf("无法找到该元素\n");
  }
  return 0;
}

二.有序二维数组的查找

--在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。输入一个数，判断二维数组中是否含有该元素，若有，输出其下标。

· ·将目标元素和右上角的元素进行比较。若目标元素小于右上角的元素，则该元素比右上角元素所在列的所有元素都小；若目标元素大于右上角的元素，则该元素比右上角元素所在行的所有元素都大。

//2.二维数组查找
#include<stdio.h>
int main()
{
   int arr[4][4] =
   { 2 ,3 ,4 ,5,
    6 ,7 ,8 ,9,
    10,11,12,13,
    14,15,16,17 };
   int row = 0;
   int col = 3, n;
   scanf("%d", &n);
   while (n != arr[row][col] && row>=0 && row<4 && col>=0 && col<4)
   {
      if (arr[row][col]>n)
      {
         col--;
      }
      else
      {
         row++;
      }
   }
   if (n == arr[row][col])
   {
      printf("找到了，该元素下标为%d %d\n", row, col);
   }
   else
   {
      printf("无法找到该元素\n");
   }
   return 0;
}

三.无序数组局部最小值查找

--求一个无序数组中的任意一个局部最小值，该数组中相邻两个元素都不相等

#include<stdio.h>

int Check(int sz, int arr[])
{
  int left = 0;
  int right = sz - 1;
  if (arr[left] < arr[left + 1])
  {
    return left;
  }
  else if (arr[right] < arr[right - 1])
  {
    return right;//判断两端
  }
  else//利用二分判断中间
  {
    while (left <= right)
    {
      int mid = left + (right - left) / 2;
      if ((arr[mid] < arr[mid - 1]) && (arr[mid] < arr[mid + 1]))
      {
        return mid;
      }
      else if (arr[mid] < arr[mid - 1] && arr[mid]>arr[mid+1])
      {
        left = mid + 1;
      }
      else//(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1]) || (arr[mid]>arr[mid-1] && arr[mid]<arr[mid+1])
      {
        right = mid - 1;
      }
    }
  }
}

int main()
{
  int arr[] = { 9,8,9,7,5,2,3,7 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  int ret = Check(sz, arr);
  printf("该数组存在一个局部最小值，该元素下标为%d\n", ret);
  return 0;
}

四.旋转数组查找

--旋转数组的定义：

排好序的数组 nums 在某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

--给定一个旋转数组，找出其最小元素并输出其下标

//旋转数组的查找
//找出一个旋转数组中的最小元素

#include<stdio.h>
int main()
{
  int arr[] = { 5,6,1,2,3,4 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  int left = 0;
  int right = sz - 1;
  while (left <= right)
  {
    int mid = left + (right - left) / 2;
    if (arr[mid]>arr[right])//在左半部分
    {
      left = mid + 1;
    }
    else if (arr[mid]<arr[right])//在右半部分
    {
      right = mid;//不能mid-1,因为mid很可能是最小值
    }
    else
    {
      printf("该数组最小元素下标为%d\n", right);
      break;
    }
  }
  return 0;
}