java数组(折半查找)-java读书笔记

数组(折半查找)

//需求：查找key在数组中第一次出现的位置，如果不存在就返回-1。

class Test

{

public static void main(String[] args)

{

int[] arr={2,4,5,7,19,32,45};

int index=halfSearch_2(arr,32);

System.out.println("index="+index);

}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

//通常

public static int getIndex(int[] arr,int key)

{

for(int x=0;x
{

if(arr[x]==key)

return x;

}

return -1;

}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

//方法1

public static int halfSearch_1(int[] arr,int key)

{

int min,max,mid;

min=0;

max=arr.length-1;

mid=(max+min)/2;

while(arr[mid]!=key)

{

if(min>max)

return -1;

if(key>arr[mid])

min=mid+1;

else if(key
max=mid-1;

mid=(max+min)/2;

}

return mid;

}

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

//方法2

public static int halfSearch_2(int[] arr,int key)

{

int min=0,max=arr.length-1,mid;

while(min<=max)

{

mid=(max+min)>>1;

if(key>arr[mid])

min=mid+1;

else if(key
max=mid-1;

else

return mid;

}

return -1;

}

}

本文来源 我爱IT技术网 http://www.52ij.com/jishu/5574.html 转载请保留链接。