how to do binary search on array which is the numbers on even indexes are ascending and the numbers on odd indexes are descending example the array {-3,10,0,9,5,0,7,-1} and i want to find a number : x=5

i think i should do binary search on even indexes alone, and on odd indexes alone

CodePudding user response：

You can use two binary searches, one for the increasing and decreasing values each. There will be a few simple modifications:

1. The bounds will not be [0, n-1] (where n is the length of array). The opening and closing limit will be different for the descending and ascending values respectively.
2. Instead of adjusting low = mid 1 or high = mid - 1, you'll use low = mid 2 and high = mid - 2 so that the parity of the middle index doesn't change during the search.

Since this is a simple task, I'll leave the formal algorithm for the reader to figure out.

CodePudding user response：

You are right, you can perform two separate binary searches. One on

(-3,0,5,0,7)

and the other on

(-1,0,9,10).

As regards the implementation, you can use a standard algorithm and

• replace all indexes by their double (i becomes 2i) for the first search;

• replace all indexes by m-2i where m is n or n-1, whichever is odd for the second search.

You cannot do with a single search, replacing the even indexes by 2i and the odd ones by m-2i because there is no guarantee that this would correspond to a growing sequence (e.g. (-3,-1,0,0,5,9,7,10)). A preliminary merge is required, taking linear time.