给定一个排序的数组 . 我们需要使用二进制搜索在数组中找到元素x .
MyApproach:
我实现了二进制搜索如下 .
检查3例1)中间元素是否== x
2)元素是否小于中间元素 . 然后,将搜索空间减少到end = mid-1
3)元素是否小于中间元素 . 然后,将搜索空间减少到start = mid 1
我使用了开始<= end,以便在剩下一些元素或者开始==结束时 . 那么,在这种情况下只剩下一个元素 .
我实现了这个,但我没有得到ExpectedOutput
任何人都可以指导我为什么? @编辑
My Main Method
public static void main(String s[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the number of testcases");
int T=sc.nextInt();
for(int i=0;i<T;i++)
{
System.out.println("Enter the size of array");
int n=sc.nextInt();
int ar[]=new int[n];
System.out.println("Enter the elements of array");
for(int j=0;j<n;j++)
{
//System.out.println("Enter the elements of array");
ar[i]=sc.nextInt(); //the elements should be entered in sorted order
}
System.out.println("Enter the element to be searched");
int x=sc.nextInt();
int a=binarySearch(ar,x);
System.out.println("the element is at index"+"::"+a);
}
sc.close();
}
public static int binarySearch(int[] ar,int x)
{
int start=0,end=ar.length-1;
int mid=0;
while(start<=end)
{
mid=start+(end-start)/2; //To avoid Overflow
if(ar[mid]==x)
return mid;
else if(x<ar[mid])
{
end=mid-1;
}
else
{
start=mid+1;
}
}
return -1;
}
Input Element Searched ExpectedOutput MyOutput
5 8 3 -1
6
7
8
1 回答
Important thing is, this algorithm will work only on sorted array. 问题如下
在下面的代码中你放了
ar[i]
而不是ar[j]