data structures using printf("\ % does not exist in the array"num)return binary search binary search is searching algorithm that works efficiently with sorted list the mechanism of binary search can be better understood by an analogy of telephone directory when we are searching for particular name in directorywe first open the directory from the middle and then decide whether to look for the name in the first part of the directory or in the second part of the directory againwe open some page in the middle and the whole process is repeated until we finally find the right name take another analogy how do we find words in dictionarywe first open the dictionary somewhere in the middle thenwe compare the first word on that page with the desired word whose meaning we are looking for if the desired word comes before the word on the pagewe look in the first half of the dictionaryelse we look in the second half againwe open page in the first half of the dictionary and compare the first word on that page with the desired word and repeat the same procedure until we finally get the word the same mechanism is applied in the binary search nowlet us consider how this mechanism is applied to search for value in sorted array consider an array [that is declared and initialized as int [{ }and the value to be searched is val the algorithm will proceed in the following manner beg end mid ( )/ nowval and [mida[ [ is less than valthereforewe now search for the value in the second half of the array sowe change the values of beg and mid nowbeg mid end mid ( )/ = / val and [mida[ [ is less than valthereforewe now search for the value in the second half of the segment soagain we change the values of beg and mid nowbeg mid end mid ( )/ nowval and [mid in this algorithmwe see that beg and end are the beginning and ending positions of the segment that we are looking to search for the element mid is calculated as (beg end)/ initiallybeg lower_bound and end upper_bound the algorithm will terminate when [midval when the algorithm endswe will set pos mid pos is the position at which the value is present in the array howeverif val is not equal to [mid]then the values of begendand mid will be changed depending on whether val is smaller or greater than [mid(aif val [mid]then val will be present in the left segment of the array sothe value of end will be changed as end mid (bif val [mid]then val will be present in the right segment of the array sothe value of beg will be changed as beg mid finallyif val is not present in the arraythen eventuallyend will be less than beg when this happensthe algorithm will terminate and the search will be unsuccessful figure shows the algorithm for binary search in step we initialize the value of variablesbegendand pos in step while loop is executed until beg is less than or equal to end in step the value of mid is calculated in step we check if the array value at mid is equal to val (item to be searched in the arrayif match is