Search Algorithms

Search Problems

Search An element in sorted And Rotated Array

-

-

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;

            }

-

-


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
-

-
Distinct pair with difference K

-

-

First Occurance in Sorted Array
-

-

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.

-

-

Binary Search

-

-

Linear Search

-

-