Help Rahul (Binary Search) Question

#1

If a[s] < key and key > a[m] how can you apply binary search?
How can tell s=mid+1 where e=n-1 while is smaller than s?
And the same thing if a[e]>key and key <a[m]. The array from a[s] to a[m-1] is not sorted.

#2

Hello @alien,

You have to start the same way as you do for binary search i.e. find the middle element.
After that, all you have to do is to check whether array at the left side or the right side of the middle element is sorted.
for left side: a[s]<a[mid]
for right side: a[mid]<a[e]
Once you have found the sorted side, just check if the element is present in the sorted:
if it present then continue for that sorted part of the array
else continue for the unsorted part.
To check if an element is present in the sorted part:
left part is sorted: a[s] <= key and key > a[m]
right part is sorted: a[mid] < key and key >= a[e]

Using the above criteria and binary search methodology in O(log N) time

  1. Find middle point mid = (l + h)/2
  2. If key is present at middle point, return mid.
  3. Else If arr[l…mid] is sorted
    a) If key to be searched lies in range from arr[l]
    to arr[mid], recur for arr[l…mid].
    b) Else recur for arr[mid+1…h]
  4. Else (arr[mid+1…h] must be sorted)
    a) If key to be searched lies in range from arr[mid+1]
    to arr[h], recur for arr[mid+1…h].
    b) Else recur for arr[l…mid]

Hope, this would help.
Give a like if you are satisfied.