数组查找操作

数组常见的查找操作如下：

1. 需求：给一个数组，查找某个元素在数组中的位置，如果该元素不存在，则返回-1。
   //正常查找元素
   public int getIndex(int[] arr, int key) {
   for(int i=0; i<arr.length-1; i++) {
   if(key==arr[i])
   return i;
   }
   return -1;
   }
   特点：通用，从第一个元素开始依次比较，效率一般
2. 需求：给一个有序数组，查找某个元素在数组中的位置，如果该元素不存在，则返回-1。
   方式1：
   public int getIndex(int[] arr, int key) {
   int min=0;
   int max=arr.length-1;
   while(min<=max) {
   int mid=(min+max)/2;
   if(key>arr[mid])
   min=mid+1;
   else if(key<arr[mid])
   max=mid-1;
   else
   return mid;
   }
   return -1;
   }
   方式2：
   public int getIndex(int[] arr, int key) {
   int min=0;
   int max=arr.length-1;
   int mid=(min+max)/2;
   while(key!=arr[mid]) {
   if(key>arr[mid])
   min=mid+1;
   else if(key<arr[mid])
   max=mid-1;
   if(min>max)
   return -1;
   mid=(min+max)/2;
   }
   return mid;
   }
   特点：快速排序的前提是数组有序，效率高。
3. 需求：给一个有序数组，将一个元素插入数组中保证数组有序。
   public int getIndex(int[] arr, int key) {
   int min=0;
   int max=arr.length-1;
   while(min<=max) {
   int mid=(min+max)/2;
   if(key>arr[mid])
   min=mid+1;
   else if(key<arr[mid])
   max=mid-1;
   else
   return mid;
   }
   return min;
   }
   思路：先查找该元素是否存在数组中，如果存在，返回在数组中的索引，如果不存在，数组不能再折半情况下，返回数组的最小索引。