查找算法之数组中超过一半的数字

题目：一个无序数组中有一个数出现的次数超过数组长度的一半，找出该值。如{1,2,3,2,4,2,5,2}，值为2。
思想：如果数组是有序的，那么出现次数超过一半的值一定是它的中位数，因此一种方法就是全排序，然后中间的那个数就是要找的值。
还有一种方法就是将上述问题转化为找中位数的问题。这时候就可以用快排的思想了，不断的左右排序，直到找到基准值所在的位置是n/2，这时候左右达到平衡。如果基准值小于n/2，那么中位数一定在右边，于是继续从右边找，如果大于n/2，那么中位数一定在左边，那么就在左边找，如此递归，直到找到为止。总的思想还是快排。

public int findUsingQuickSort(int[] arr, int start, int end){
  int low = start;
  int high = end;
  int key = arr[start];
  while(low < hight){
    while(low<high && arr[high]>key){
        high--;
    }
  arr[low]=arr[high];
  while(low<high && arr[low]<key){
        low++;
    }
  arr[high]=arr[low];
  }
  arr[low] = key;  
  if(low==(arr.length-1)/2){
    return arr[(arr.lenght-1)/2]
   }else if(low<(arr.length-1)/2)
    return findUsingQuickSort(arr, low+1, end);
  }else if(low > (arr.lenght-1)/2){
    return findUsingQuickSort(arr, start, low-1);
  }
return -1;
}