Leetcode QOTD:- 33. Search in Rotated Sorted Array

Normally binary search works only on fully sorted arrays, but here one half is always sorted, and that is the key logic.

Main Idea

At every step:

1. Find mid
2. Check which half is sorted
3. Decide whether target lies inside that sorted half
4. Move accordingly

why this approach?

In a rotated sorted array:

• At least one half is always sorted.
• Using that sorted half, we can decide where target can exist.
• So every iteration removes half the array.

complexity:

Time: O(log n)
Space: O(1)

class Solution {
    public int search(int[] a, int t) {

        int low = 0, high = a.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == t) {
                return mid;
            }
            if (a[low] <= a[mid]) {
                if (a[low] <= t && t <= a[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if (a[mid] <= t && t <= a[high]) {
                    low=mid+1;
                }else{
                    high=mid-1;
                }
            }
        }
        return -1;
    }
}