Binary Search (using while loop and using recursion)

# Binary Search:

Binary Search is the searching technique, which works on the divide and conquers algorithm and it works only for sorted arrays. 

Binary Search is a searching algorithm. In each step, the algorithm compares the input element x with the value of the middle element in the array. If the values match, return the index of the middle. Otherwise, if x is less than the middle element, then the algorithm recurs for the left side of the middle element, else recurs for the right side of the middle element. 

Suppose below is the array in which we want to search the key 53.

For searching any element in the array, We need below three variables:

Low // Contains the lower index of Array

Mid // Contains the Mid Index of Array

High // Contains the Higher Index of Array

So initially Low will be 0 and High will be (length - 1) length of below array is 21(number of items in the array),

So High will be 20.

Low = 0;

High = 20; // length - 1 = 21 - 1

Mid = 10; //((Low + High) / 2) as Low is 0 and High is 20, So (0 + 20)/2 = 10

Now we will compare the key 53 to A[Mid], which is 31 (A[10]) and 31 != 53 and key 53 is greater than 31 (A[Mid]), So our key should be in the right of index 10 (Mid) as the array is sorted and key 53 is greater than A[Mid]. 

(Key) 53 > 31 (A[Mid])

So now, we have to update our Low to (Mid + 1), Low = 10 + 1 = 11; 



 


 Now again calculate the Mid, So Mid = (Low + High)/2 = (11 + 20)/2 = 15, 

Low = 11;

Mid = 15;

High = 20;


 


Now we will compare the key 53 with A[Mid], which is 53.

(Key) 53 == 53 (A[Mid])

So our Key has been found, So now we can say that the Key(53) is found at index 15. 

Suppose in the first iteration the key 53 is lesser than the Mid Value than we have to update the High as High = Mid – 1, As in that case our Key should be in the left Index of Mid.

# Algorithm/Function for Binary Search using while loop:

int binarySearchUsingLoop(struct Array objArr, int iKey)
{
    int iHigh = objArr.iLength - 1;
    int iLow = 0;
    int iMid = 0;
    int iReturnIndex = -1;

    while (iHigh >= iLow)
    {
       iMid = floor( ( ( iHigh + iLow ) / 2 ) );

       if (objArr.A[iMid] == iKey)
       {
           iReturnIndex = iMid;
           break;
       }
       else if (iKey < objArr.A[iMid])
       {
            iHigh = iMid - 1;
       }
       else
       {
           iLow = iMid + 1;
       }
    }

    return iReturnIndex;
}

# Algorithm/Function for Binary Search using recursion:

int binarySearchUsingRecursion(struct Array objArr, int iKey, int iLow, int iHigh)
{
    int iMid = 0;
    int iReturnIndex = -1;

    while (iHigh >= iLow)
    {
       iMid = floor( ( ( iHigh + iLow ) / 2 ) );

       if (objArr.A[iMid] == iKey)
       {
           iReturnIndex = iMid;
           break;
       }
       else if (iKey < objArr.A[iMid])
       {
            return binarySearchUsingRecursion(objArr, iKey, iLow, (iMid - 1));
       }
       else
       {
            return binarySearchUsingRecursion(objArr, iKey, (iMid + 1), iHigh);
       }
    }

    return iReturnIndex;
}

Note: Full program can be downloaded from the link below:

https://github.com/VChaudhary854/LearnDataStructureWithVishal/tree/DataStructurePrograms

You can also follow this link for more.

 


Comments

Post a Comment

Popular posts from this blog

Insert an element in a sorted array

Image
# Insert an element in a sorted array: To insert an element in a sorted array, We have to start comparing the key element with the last element of the array and if the last element is greater than the key element then shift the last element to its next index. This procedure we have to follow until we find the element in array equal to or smaller than the key element. like if we need to insert 5 in below array: then we have to take a variable "i" and "i" will be initialized by array length - 1 So i = A.length - 1 = 5 - 1 = 4; So 5 is compared with A[4], as A[4] is 8 so 8 > 5 , then we have to shift A[i] to A[i+1], A[i+1] = A[i] // A[5] = A[4] // A[5] = 8  and A[4] is empty. and need to do --i, so i will be 3 now now again we have to compare 5 with A[3], as A[3] is 7 and 7 > 5 , So again we have to shift it to the next index. A[i+1] = A[i]; // A[4] = A[3] // A[4] = 7  and A[3] is empty. --i; So i will be 2 now now again we have to compare 5 with A[2], as A[2] is...
Read more

Finding the length of a string in c and c++

Image
# Finding the length of a string in c and c++: # What is a string: A string is a set of characters and string is terminated by a '\0' character. This character is used to know the termination of the string. So to find the length of the above string. We have to traverse this string till we find the '\0'. Please check the below program for more details: # include < iostream > using namespace std ; int main () {      /*   * No need to append '\0' as this is   * added by Compiler automatically as we use "".   */ char * s = "welcome" ; int iLength = 0 ; while ( s [ iLength ] != '\0' ) { ++ iLength ; } cout << "The Length of the string is: " << iLength << endl ; return 0 ; } # Output of the program: Note: Full program can be downloaded from the link below: https://github.com/VChaudhary854/LearnD...
Read more

Transposition Linear Search

Transposition Linear Search: In this algorithm of searching, If the key is found then the key is swapped with the item at (keyIndex - 1) or the item before the search item. The idea behind this algorithm is to move most search item/key to front/head of the array with each search. So that if the same item gets search again then it will take less time to search. Below is the program for this algorithm of searching: # include < iostream > using namespace std ; /** * @brief swap: This function swaps the items. * @param pFirst: First item. * @param pSecond: Second item. */ void swap ( int * pFirst , int * pSecond ) { int iTemp ; iTemp = * pFirst ; * pFirst = * pSecond; * pSecond = iTemp ; } /** * @brief LinearSearch: This methods search the Key in the array passed in first param, * and if item/key is found then, swap it with the item at 1 less index. * @param objArr: object o...
Read more