Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class Arrays
- {
- public static void clearScreen()
- {
- System.out.print('\u000C');
- }
- public static int equal (Integer a[], int b[])
- {
- mergeSort(a);
- int i=0;
- int ans=-1;
- do
- {
- int target = b[i]+b[i+1];
- ans=binarySearch(a,target);
- i++;
- if(ans==1)
- return 1;
- else
- return -1;
- }
- while (ans=-1);
- return -1 ;
- }
- public static int binarySearch (Integer []a, int target)
- {
- boolean found = false;
- int lo = 0;
- int hi = a.length-1;
- int mid = 0;
- while(lo<=hi&&!found)
- {
- mid=(lo+hi)/2;
- if(a[mid]==target)
- found=true;
- else
- {
- if(target>a[mid])
- lo=mid+1;
- else
- hi=mid-1;
- }
- }
- if(found)
- return 1;
- else
- return -1;
- }
- public static void mergeSort(Comparable [ ] a)
- {
- Comparable[] tmp = new Comparable[a.length];
- mergeSort(a, tmp, 0, a.length - 1);
- }
- private static void mergeSort(Comparable [ ] a, Comparable [ ] tmp, int left, int right)
- {
- if( left < right )
- {
- int center = (left + right) / 2;
- mergeSort(a, tmp, left, center);
- mergeSort(a, tmp, center + 1, right);
- merge(a, tmp, left, center + 1, right);
- }
- }
- private static void merge(Comparable[ ] a, Comparable[ ] tmp, int left, int right, int rightEnd )
- {
- int leftEnd = right - 1;
- int k = left;
- int num = rightEnd - left + 1;
- while(left <= leftEnd && right <= rightEnd)
- if(a[left].compareTo(a[right]) <= 0)
- tmp[k++] = a[left++];
- else
- tmp[k++] = a[right++];
- while(left <= leftEnd) // Copy rest of first half
- tmp[k++] = a[left++];
- while(right <= rightEnd) // Copy rest of right half
- tmp[k++] = a[right++];
- // Copy tmp back
- for(int i = 0; i < num; i++, rightEnd--)
- a[rightEnd] = tmp[rightEnd];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement