0

For an unsorted array, I want to know the elements that can be found using binary search. Can I achieve this without actually binary searching for each of the elements?

For example here's an binary search algorithm

def binary_search(arr, low, high, x): 

    if high >= low: 

        mid = (high + low) // 2

        if arr[mid] == x: 
            return mid 

        elif arr[mid] > x: 
            return binary_search(arr, low, mid - 1, x) 

        else: 
            return binary_search(arr, mid + 1, high, x) 

    else: 
        return -1

For example my input is [3,5,4,8,7,6,10], output will be [3,5,8,10], because

binary_search(lst, 0,6,3)
0
binary_search(lst, 0,6,5)
1
binary_search(lst, 0,6,4)
-1
binary_search(lst, 0,6,8)
3
binary_search(lst, 0,6,7)
-1
binary_search(lst, 0,6,6)
-1
binary_search(lst, 0,6,10)
6

That is, only the numbers 3,5,8,10 can be found.

sofaruntitled
  • 275
  • 1
  • 2
  • 6
  • 1
    For an unsorted array, how can you guarantee you can find anything with binary search? – ggorlen Jul 23 '20 at 20:39
  • 2
    It seems like you are accumulating values that are greater than the ones that were found so far. It could be done, but I doubt it's called "binary search"... – iAmOren Jul 23 '20 at 20:39
  • you can check this [answer](https://stackoverflow.com/questions/35895627/can-we-use-binary-search-with-an-unsorted-array) for information – Vijay Bhati Jul 26 '20 at 19:10

0 Answers0