赞
踩
四五月份找实习的时候,在去哪儿的现场笔试题上有一道循环有序的查找问题,当时用了最简单粗暴的方法解决这个问题,就是for循环解决的,当时也算运气好,没想实现的效率,只是纯粹的想实现这个功能,还好有面试的机会,但在面试的时候这个问题还是被问到了,当时没准备好,没回答出来,接连几个问题都没回答出来,最终挂掉了.现在来总结一番.
这个是java的解决方法.之后再附上python的方法,感觉上更加简洁,供大家参考吧
- package com.pingan.mhc.bishiti;
- /**
- *
- * @author MENGHUCHENG012
- *
- */
- public class ChangeBinary {
-
- public static int CycleBinary(int[] array,int key){
- int left = 0;
- int right = array.length-1;
- while(left <= right){
- int mid = left +(right-left)/2;
- if(array[mid]==key){
- return mid;
- }
- if(array[left]<array[mid]){
- if(array[left]<key&&key<array[mid]){
- right = mid - 1;
- }else{
- left = mid + 1;
- }
- }else{
- if(array[left]>key && key>array[mid]){
- left = mid + 1;
- }else{
- right = mid - 1;
- }
-
- }
- }
-
- return -1;
- }
-
-
- public static void main(String[] args) {
- int[] a = new int[]{23,28,19,27};
- int num = CycleBinary(a,27);
- if(num != -1){
- System.out.println("已经找到了,位置在"+num);
- }else{
- System.out.println("没有找到该值");
- }
- }
-
- }
python版本的
- #encoding:utf-8
- #python版本的
- def CycleBinary(array,key):
- left = 0
- right = len(array)-1
- while left<=right:
- #下面这句写在循环里面
- mid = left+(right-left)/2
- if key == array[mid]:
- print "找到"
- return mid
- if array[left]<=array[mid]:#从小到大排序,说明边界在右边
- if array[left]<=key and key<=array[mid]:
- right = mid - 1
- else:
- left = mid + 1
- else:
- if array[left]>=key and key>=array[mid]:#边界在左半边,右边有序
- left = mid + 1
- else:
- right = mid - 1
- print "找不到"
- return -1
-
- data = (11,31,87,99,2,5,7,8)
- CycleBinary(data,2)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。