思路:二分法思想,先找出该数存在的某段有序数组中,随意取一个下边,它的左边和右边总有一个是有序的段,而如果这个查找的数刚好在这个段中,就可以利用二分法了。
class XuanZhuanYouXuChaZhao { public int Find(int[] datas,int num) { int left = 0; int right = datas.Length - 1; int mid = 0; while (true) { if (left > right) return -1; mid = (left + right) / 2; if (num == datas[mid]) return mid; if (datas[mid] > datas[left])//左边有序 { if (num < datas[mid] && num >= datas[left]) { //左边二分法 right = mid - 1; break; } else { //在右边 继续找有序 left = mid + 1; } } else//右边有序 { if (num > datas[mid] && num <= datas[right]) { //右边二分法 left = mid + 1; break; } else { //在左边,继续查找有序 right = mid - 1; } } } //二分法查找 while (left <= right) { mid = (left + right) / 2; if (num == datas[mid]) return mid; if (num > datas[mid])//右边找 { left = mid + 1; } else//左边找 { right = mid - 1; } } return -1; } }
//旋转有序数组中查找 static void TestXuanZhuanYouXuChaZhao() { XuanZhuanYouXuChaZhao XZY = new XuanZhuanYouXuChaZhao(); int[] datas = {20,50,90,2,5,9,11,18,19 }; int[] datas2 = { 300,500,1,2,3,4,5,6,7,8,9,10,11,13,15,18,22,30,38,40,45,55,66,77,88 }; Console.WriteLine(XZY.Find(datas, 18));//7 Console.WriteLine(XZY.Find(datas, 20));//0 Console.WriteLine(XZY.Find(datas2, 9));//10 Console.WriteLine(XZY.Find(datas2, 77));//23 Console.WriteLine(XZY.Find(datas2, 22));//16 }