二分查找的相关算法题，android 移动应用基础教程
按 照上述的思路，我们的第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最后第一个指针将指向前面子数组的最后一个元素， 而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。这就是循环结束的条件。
核心实现代码：
int Min(int *numbers , int length)
{
if(numbers == NULL || length <= 0)
return;
int index1 = 0;
int index2 = length - 1;
int indexMid = index1;
while(numbers[index1] >= numbers[index2])
{
if(index2 - index1 == 1)
{
indexMid = index2;
break;
}
indexMid = (index1 + index2) / 2;
//如果下标为 index1、index2 和 indexMid 指向的三个数字相等，则只能顺序查找
if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
return MinInOrder(numbers , index1 , index2);
if(numbers[indexMid] >= numbers[index1])
index1 = indexMid;
else if(numbers[indexMid] <= numbers[index2])
index2 = indexMid;
}
return numbers[indexMid];
}
//顺序查找
int MinInOrder(int *numbers , int index1 , int index2)
{
int result = numbers[index1];
for(int i = index1 + 1 ; i <= index2 ; ++i)
{
if(result > numbers[i])
result = numbers[i];
}
return result;
}
注意：当两个指针指向的数字及他们中间的数字三者相同的时候，我们无法判断中间的数字是位于前面的字数组还是后面的子数组中，也就无法移动两个指针来缩小查找的范围。此时，我们不得不采用顺序查找的方法。
2 旋转数组中查找某个数字
要求
给定一没有重复元素的旋转数组（它对应的原数组是有序的），求给定元素在旋转数组内的下标（不存在的返回-1）。
例如
有序数组为｛0，1，2，4，5，6，7｝，它的一个旋转数组为｛4，5，6，7，0，1，2｝。
元素 6 在旋转数组内，返回 2
元素 3 不在旋转数组内，返回-1
分析
遍历一遍，可以轻松搞定，时间复杂度为 O(n)，因为是有序数组旋转得到，这样做肯定不是最优解。有序，本能反映用二分查找，举个例子看看特点
可以看出中间位置两段起码有一个是有序的（不是左边，就是右边），那么就可以在有序的范围内使用二分查找；如果不再有序范围内，就到另一半去找。
参考代码
int search(int A[], int n, int target) {
int beg = 0;
int end = n - 1;
while (beg <= end)
{
int mid = beg + (end - beg) / 2;
if(A[mid] == target)
return mid;
if(A[beg] <= A[mid])
{
if(A[beg] <= target && target < A[mid])
end = mid - 1;
else
beg = mid + 1;
}
else
{
if(A[mid] < target && target <= A[end])
beg = mid + 1;
else
end = mid - 1;
}
}
return -1;
}
扩展
上边的有求是没有重复的元素，现在稍微扩展下，可以有重复的元素，其他的要求不变。
思路
大致思路与原来相同，这是需要比较 A[beg] 与 A[mid]的关系
A[beg] ?< A[mid] ————左边有序
A[beg] ?> A[mid] ————右边有序
A[beg] ?= A[mid] ————++beg
boolean search(int A[], int n, int target) {
int beg = 0;
int end = n - 1;
while (beg <= end)
{
int mid = beg + (end - beg) / 2;
if(A[mid] == target)
return true
《Android 学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
【docs.qq.com/doc/DSkNLaERkbnFoS0ZF】 完整内容开源分享
;
if(A[beg] < A[mid])
{
if(A[beg] <= target && target < A[mid])
end = mid - 1;
else
beg = mid + 1;
}
else 0if(A[beg] > A[mid])
{
if(A[mid] < target && target <= A[end])
beg = mid + 1;
else
end = mid - 1;
}
else
++beg;
}
return false;
}
3 数字在排序数组中的出现次数
//二分查找，二分查找 key 第一次出现的位置，二分查找最后一次出现的 key
//返回两者相减+1 或者找到第一次出现的位置，向后查找
int binarySearchFirstPos(int * iArr, int l, int h, int key)
{
while(l <= h )
{
int mid = (l + h) / 2;
if(iArr[mid] < key)
l = mid +1;
elseif(iArr[mid] > key)
h = mid - 1;
else
{
if(mid == l || iArr[mid - 1] != key)
return mid;
else
h = mid - 1;
}
}
return -1;
}
int binarySearchLastPos(int * iArr, int l, int h, int key)
尾声
最后，我再重复一次，如果你想成为一个优秀的 Android 开发人员，请集中精力，对基础和重要的事情做深度研究。
对于很多初中级 Android 工程师而言，想要提升技能，往往是自己摸索成长，不成体系的学习效果低效漫长且无助。 整理的这些架构技术希望对 Android 开发的朋友们有所参考以及少走弯路，本文的重点是你有没有收获与成长，其余的都不重要，希望读者们能谨记这一点。
这里，笔者分享一份从架构哲学的层面来剖析的视频及资料分享给大家梳理了多年的架构经验，筹备近 6 个月最新录制的，相信这份视频能给你带来不一样的启发、收获。
Android 进阶学习资料库
一共十个专题，包括了 Android 进阶所有学习资料，Android 进阶视频，Flutter，java 基础，kotlin，NDK 模块，计算机网络，数据结构与算法，微信小程序，面试题解析，framework 源码！
还未添加个人签名 2021.03.19 加入
还未添加个人简介
评论