数组常见的查找操作如下：
- 需求：给一个数组，查找某个元素在数组中的位置，如果该元素不存在，则返回-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;
}
特点：通用，从第一个元素开始依次比较，效率一般 - 需求：给一个有序数组，查找某个元素在数组中的位置，如果该元素不存在，则返回-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;
}
特点：快速排序的前提是数组有序，效率高。 - 需求：给一个有序数组，将一个元素插入数组中保证数组有序。
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;
}
思路：先查找该元素是否存在数组中，如果存在，返回在数组中的索引，如果不存在，数组不能再折半情况下，返回数组的最小索引。
