30daychallenge (19) | Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Ban đầu tôi cũng khá là thắc mắc làm thế nào để implement bài này với O(logn), nếu đề bài cho chỉ số rồi bắt tìm chẳng hạn, với rotate array thì tôi sẽ tìm công thức. Nhưng đây lại cho giá trị.

Tìm kiếm phị phân ? Trên một mảng không sắp xếp ? Thực ra nếu ta mặc định mảng này là không sắp xếp thì sẽ không làm được bài này. Key của bài này ở chỗ ta hiểu mảng của đề bài luôn có thể chia làm hai phần, một phần tăng, và một phẩn giảm.

Giả sử [4,5,6,7,0,1,2] ta có thể tách thành hai phần [4,5,6,7] và [0,1,2]. Ta muốn tìm số 1 chẳng hạn. Đặt left =0, right = 6. Chọn random một phần tử nằm giữa, tôi chọn mid = (left+right+1)/2. Trong trường hợp này, mid = 3. Ở đây nums[mid] = 7 > nums[left]. Vậy nếu target ta chọn nằm trong vị trí này, tức nums[left] <= target < nums[mid]. thì right = mid -1. Ngược lại, left = mid +1 . Tương tự như thế với trường hợp sau.

Tóm lại, ta hiểu là target sẽ phải nằm trong 1 đoạn left -> mid hoặc mid -> right. Mỗi đoạn lại có 2 điều kiện khác nhau.

Đây là code trên Java:


Hẹn gặp lại bạn ở những bài viết sau. Cảm ơn bạn !