一.寻找有序数组中的元素
--寻找一个有序数组中的某个元素，并输出其下标
//寻找有序数组中的某个元素
#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] 。
--给定一个旋转数组，找出其最小元素并输出其下标
//旋转数组的查找
//找出一个旋转数组中的最小元素
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen )
{
//二分法找局部最小值
int left = 0;
int right = rotateArrayLen - 1;
int ret = 0;
int mid = 0;
while(left <= right)
{
mid = left + (right - left) / 2;
if(rotateArray[mid] > rotateArray[right])
{
//在左半部分
left = mid + 1;
}
else if(rotateArray[mid] < rotateArray[right])
{
//在右半部分
right = mid;
}
else
{
//相等，去重
right--;
}
}
return rotateArray[mid];
}
