`
wuqiwei
  • 浏览: 20949 次
最近访客 更多访客>>
社区版块
存档分类
最新评论

黑马程序员—数组(折半查找及相关面试题)

 
阅读更多

 ------- android培训java培训、期待与您交流! ----------



 

 

 

 

class ArrayTest4//数组(折半查找) 
{	
//1:普通的做法 需要从头开始找 效率低

//public static int getIndex(int[] arr,int key);加上了;就致命了 提示一大推见截图
public static int getIndex(int[] arr, int key)
//在公共类中打印时也不要忘了是int index = getIndex_2(arr,190);不是getInddex_2(190)
{
		for (int x=0;x<arr.length;x++ )
		{
			if (arr[x]==key)//是==
			{
				return x;//找的是位置 所以是x 不是key
			}				
		}
		return -1;
	}
//2:折半查找 第一种形式	效率高 但是必须要保证该数组是有序的数组 
	public static int halfSearch(int []arr,int key)//返回值是int
	{
		int min,max,mid;
		/*arr[min]=0;
		arr[max]=arr.length-1;
		arr[mid]=(arr[min]+arr[max])>>1;  错误的*/
		
		min=0;
		max=arr.length-1;
		mid=(min+max)/2;

		while (key!=arr[mid])/*当mid不等于key时 才会执行循环 如果循环没有找到"!=" 
							  就说明 mid就是key*/
		{
			if (key>arr[mid])//不是arr[min]
			{
				min=mid+1;
			}
			else if (key<arr[mid])//对流程控制掌握不熟 不能是else 
			{
				max=mid-1;
			}
			if (min>max)//min指的是最小角标位 不是具体值 这句就是为key不在数组中准备的
			{	
				return -1;
			}
				mid=(min+max)/2;/*注意此句不能丢 在判断完 key与arr[mid]的大小后
				还要继续折半写这里是找到key值(见图示)循环终止的意思 且此句不能
				放到上面的if执行语句中(因为没有mid)*/
		}
			return mid;
	}
//3.折半查找 第二种形式 (总结第一种形式 再优化下就是)

public static int halfSearch_2(int[] arr,int key)
	{
		int min=0,max=arr.length-1,mid;

		while (min<=max)//41行的反向思考
		{
			mid = (max+min)>>1;//在这里写mid=(max+min)>>1 就不用总是像1那样重复了
			if (key>arr[mid])
			{
				min=mid+1;
			}
			else if (key<arr[mid])
			{
				max=mid-1;
			}
			else
				return mid;//这里不能直接写return 因为else if是没有条件后的操作的
		}
		return -1;
	}
/*
面试题:有一个有序的数组,想要将一个元素插入到该数组中,
还要保证该数组是有序的。如何获取该元素在数组中的位置。

思路: 其实就是最后不返回-1 返回min 即可 因为按照二的方法在int[] arr
= {2,4,5,7,19,32,45};数组中查看8是否存在结果是 最后返回 -1
但是要想一下 其实-1的结果是经过循环过程的 所以利用假设的思想
无论插入那一个数他都会自动地去寻找最适合放自己的位置 也就是
折半的过程展示 所以最后的min所在角标位就是要插入的最佳位置

面试可能不考程序 会问怎么办
答案:利用折半的形式查找该数在数组中的位置 存在就在存在的位置
上插入即可 不存在就返回最小的角标值 就是该位置
*/

	public static void main(String[] args) 
	{	
		//int[] arr = {3,2,1,34,8,9};
 		//int index = getIndex(arr,34);
 		//System.out.println("index="+index);

		int[] arr = {1,4,6,7,9,23,46};
		int index=halfSearch_2(arr,46);
		System.out.println("index="+index);
		
		System.out.println("Hello World!");
	}
}

 

 

  • 大小: 37.2 KB
  • 大小: 46.6 KB
  • 大小: 29.7 KB
  • 大小: 15.6 KB
  • 大小: 1.3 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics