Search Algorithms

Search Problems

Search An element in sorted And Rotated Array

-

	/**
	* Duplicates are not allowed in arr.
	*/
	public int search(int arr[],int search){
	int low =0;
	int high = arr.length-1;
	while(low <= high){
	int mid = (low + high)/2;
	if(arr[mid] == search){
	return mid;
	}
	if(arr[mid] < arr[high]){
	if(arr[mid] < search && search <= arr[high]){
	low = mid+1;
	}else{
	high = mid-1;
	}
	}else{
	if(search >= arr[low] && search < arr[mid]){
	high = mid-1;
	}else{
	low = mid+1;
	}
	}
	}
	return -1;
	}

view raw SearchElementInSortedAndRotatedArray.java hosted with ❤ by GitHub

-

Find missing number in arithmetic progression 

 while(low <= high){

            middle = (low + high)/2;

            if(input[middle] == input[0] + (middle)*ap){ //

                low = middle+1;

            }else if((input[middle] > input[0] + (middle)*ap) && input[middle-1] == input[0] + (middle-1)*ap){

            return input[0] + (middle)*ap;

            }else{

                high = middle-1;

            }

-

	package com.interview.binarysearch;
	/**
	* missing no in arithmetic progression
	* http://www.careercup.com/question?id=4798365246160896
	*/
	public class ArithmeticProgressionSearch {
	public int search(int input[]){
	int low =0;
	int high = input.length-1;
	int ap = (input[high] - input[low])/(input.length);
	int middle = -1;
	while(low <= high){
	middle = (low + high)/2;
	if(input[middle] == input[0] + (middle)*ap){ //
	low = middle+1;
	}else if((input[middle] > input[0] + (middle)*ap) && input[middle-1] == input[0] + (middle-1)*ap){
	return input[0] + (middle)*ap;
	}else{
	high = middle-1;
	}
	}
	return -1;
	}
	public static void main(String args[]){
	int input[] = {1,7,10,13,16,19,22};
	//int input[] = {1,3,7,9};
	ArithmeticProgressionSearch aps = new ArithmeticProgressionSearch();
	System.out.println(aps.search(input));
	//System.out.println(aps.search1(input));
	}

view raw Arithmetic.java hosted with ❤ by GitHub

-


Median of two sorted Arrays

1.Merge two arrays using while loop into third array of size n + m
2 find the median of third array

Local Extrema 

1. Element is either >= to is neigbouring elements or <= to its neigbouring elements

Peak Element
-

	package com.tvidushi.arrays;
	import java.util.stream.Stream;
	/**
	* An Array element is considered peaj ,if it is not
	* smaller than its neigbours
	*/
	public class PeakElement {
	public static void main(String[] args) {
	int num [] = {10,20,15,2,23,90,67};
	for(int i= 1; i<num.length-1;i++){
	if(num[i-1]<num[i] && num[i+1]<num[i]){
	System.out.println("Peak element are "+num[i]);
	}
	}
	}
	}

view raw PeakElement.java hosted with ❤ by GitHub

-
Distinct pair with difference K

-

	import java.util.Arrays;
	/**
	* http://www.geeksforgeeks.org/count-pairs-difference-equal-k/
	*
	* Count all distinct pairs with difference equal to k
	2.6
	Given an integer array and a positive integer k, count all distinct pairs with difference equal to k.
	Examples:
	Input: arr[] = {1, 5, 3, 4, 2}, k = 3
	Output: 2
	There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2}
	Input: arr[] = {8, 12, 16, 4, 0, 20}, k = 4
	Output: 5
	There are 5 pairs with difference 4, the pairs are {0, 4}, {4, 8},
	{8, 12}, {12, 16} and {16, 20}
	*/
	public class CountNDistinctPairsWithDifferenceK {
	public int count(int arr[],int k){
	Arrays.sort(arr);
	int count = 0;
	for(int i=0; i < arr.length; i++){
	boolean result = binarySearch(arr, i+1, arr.length-1, arr[i] + k);
	if(result){
	count++;
	}
	}
	return count;
	}
	private boolean binarySearch(int arr[],int start,int end,int num){
	if(start > end){
	return false;
	}
	int mid = (start + end)/2;
	if(arr[mid] == num){
	return true;
	}
	else if(arr[mid] > num){
	return binarySearch(arr,start,mid-1,num);
	}else{
	return binarySearch(arr,mid+1,end,num);
	}
	}
	public static void main(String args[]){
	CountNDistinctPairsWithDifferenceK cn = new CountNDistinctPairsWithDifferenceK();
	int arr[] = {1,2,3,4,5,7,9};
	System.out.print(cn.count(arr, 3));
	}
	}

view raw PairsOfDifferenceK.java hosted with ❤ by GitHub

-

First Occurance in Sorted Array
-

	public class FirstOccurrenceOfNumberInSortedArray {
	public int firstOccurrence(int input[], int x){
	int low = 0;
	int high = input.length-1;
	while(low <= high){
	int middle = (low + high)/2;
	if(input[middle] == x && (middle == 0 || input[middle-1] < x)){
	// if(input[middle] == x){
	return middle;
	}else if(input[middle] < x){
	low = middle+1;
	}else{
	high = middle-1;
	}
	}
	return -1;
	}
	public static void main(String args[]){
	FirstOccurrenceOfNumberInSortedArray fos = new FirstOccurrenceOfNumberInSortedArray();
	int input[] = {1,2,2,2,2,2,5,6,7,7};
	System.out.println(fos.firstOccurrence(input, 7));
	}
	}

view raw FirstOccuranceInSortedArray.java hosted with ❤ by GitHub

-

Missing Number in consective Array

1) Verify  num [last]- num[first] = size -1
2) Iterate & find out



Write a function to find square root of a number

Steps:

Use binary search to find the square root.

1. Initialize, start = 0, end = number, mid = (start+end)/2.

2. Set prevMid = 0, as the previous mid value.

3. Find diff = absolute difference between prevMid and mid.

4. While mid is not the square root of number (i.e. mid*mid != number) and difference diff is greater than 0.0005, 

repeat the following steps:

  a. If mid*mid > number, then the square root will be less than mid. So, set end = mid.

  b. Else, the square root will be greater than mid. So, set start = mid.

  c. Set prevMid = mid

  d. Re-evaluate mid  = (start+end)/2.

  e. Re-evaluate diff from prevMid and mid.

-

	package com.tvidushi;
	public class Squareroot {
	/*
	Steps:
	Use binary search to find the square root.
	1. Initialize, start = 0, end = number, mid = (start+end)/2.
	2. Set prevMid = 0, as the previous mid value.
	3. Find diff = absolute difference between prevMid and mid.
	4. While mid is not the square root of number (i.e. mid*mid != number) and difference diff is greater than 0.0005,
	repeat the following steps:
	a. If mid*mid > number, then the square root will be less than mid. So, set end = mid.
	b. Else, the square root will be greater than mid. So, set start = mid.
	c. Set prevMid = mid
	d. Re-evaluate mid = (start+end)/2.
	e. Re-evaluate diff from prevMid and mid.
	*/
	public static void main(String[] args) {
	int num = 1090;
	int start = 0;
	int end = num;
	int mid = (start +end)/2;
	int premid =0;
	while(mid*mid != num){
	if( (Math.abs(mid -premid) <0.0005)){
	break;
	}
	if(mid*mid>num){
	end = mid;
	premid = mid;
	mid = (start +end)/2;
	}else{
	start = mid;
	premid = mid;
	mid = (start +end)/2;
	}
	}
	System.out.println("square root is "+mid);
	}
	}

view raw Squareroot.java hosted with ❤ by GitHub

-

Binary Search

-

	import java.util.Arrays;
	public class BinarySearch {
	private int num[] ;
	private int len ;
	public void searchElement(int[] num,int x) {
	this.len= num.length;
	this.num = num;
	int mid = (0+len)/2;
	int lower = 0;
	int higher = num.length -1;
	boolean check= false;
	while(lower<= higher){
	mid = (lower+higher)/2;
	if(num[mid] == x){
	check = true;
	System.out.println("The position is :"+mid);
	break;
	}else if(num[mid]<x){
	lower = mid+1;
	System.out.println(num[mid]+"---"+ lower);
	}else if(num[mid]>x){
	higher = mid-1;
	System.out.println(num[mid]+"--**-"+ higher);
	}
	}
	if(!check) System.out.println("Element is not present");
	}

view raw BinarySearch.java hosted with ❤ by GitHub

-

Linear Search

-

	-
	public static void lsearch() {
	Integer[] inputArray = {2,3,31,24,5,6,61,7,8,92};
	Integer num = 61;
	Stream.of(inputArray).forEach(x->{
	if(x==num){
	System.out.println("Number foound at location : "+x);
	}
	});
	}

view raw LinearSearch.java hosted with ❤ by GitHub

-