【记录】代码练习-折半查找 - 黑马程序员技术交流社区

public class ArrayDemo
{
public static void main (String args [])
{
int [] arr = {1,5,6,7,9,12,45,65,789};
int index = halfSearch(arr,65);
int index2 = halfSearch_2(arr,65);
int index3 = halfSearch_3(arr,8);
System.out.println(index);
System.out.println(index2);
System.out.println(index3);
}
//折半查找1
public static int halfSearch(int [] arr, int x)
{
int min = 0;
int max = arr.length-1;
int mid = (min+max)/2;
while (arr[mid]!=x)
{
mid = (max+min)/2; //计算出mid的值，不然这个代码就没有意义。
if (x<arr[mid])
max = mid-1;
else if (x>arr[mid])
min = mid+1;
if (max<min)
return -1;
}
return mid;
}
//折半查找2
public static int halfSearch_2(int [] arr, int x)
{
int min = 0;
int max = arr.length-1;
int mid = (min+max)/2;
while (min<=max)
{
mid = (max+min)>>1; //右移一位，相当于除以2，比较快速
if (x<arr[mid])
max = mid-1;
else if (x>arr[mid])
min = mid+1;
else
return mid; //只剩下x=arr[mid]的情况，返回mid就行
}
return -1; //min>max的情况直接返回-1。
}
/*
需求：在数组{1,5,6,7,9,12,45,65,789}中，存储一个元素，
保证这个数组还是有序的，这个元素存储的位置角标怎么获取？
*/
public static int halfSearch_3(int [] arr, int x)
{
int min = 0;
int max = arr.length-1;
int mid = (min+max)/2;
while (min<=max)
{
mid = (max+min)>>1; //右移一位，相当于除以2，比较快速
if (x<arr[mid])
max = mid-1;
else if (x>arr[mid])
min = mid+1;
else
return mid; //只剩下x=arr[mid]的情况，返回mid就行
}
return min; //min现在所在的位置就是该元素应该存储的位置。
}
}

复制代码