Table of Contents
Binary Search
Regular Binary Search
Key Idea: In a normal sorted array, you can directly compare nums[middle] with target to decide whether to move left or right.
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := left + (right-left)/2
if nums[middle] == target {
return middle
} else if nums[middle] < target {
left = middle + 1
} else {
right = middle - 1
}
}
return -1 // Target not found
}Binary Search in a Rotated Sorted Array
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := left + (right-left)/2
if nums[middle] == target {
return middle
}
// Determine which side is sorted
if nums[left] <= nums[middle] {
// Left side is sorted
if nums[left] <= target && target < nums[middle] {
right = middle - 1
} else {
left = middle + 1
}
} else {
// Right side is sorted
if nums[middle] < target && target <= nums[right] {
left = middle + 1
} else {
right = middle - 1
}
}
}
return -1 // Target not found
}Git Diff
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := left + (right-left)/2
if nums[middle] == target {
return middle
}
- // Normal binary search
- if nums[middle] < target {
- left = middle + 1
- } else {
- right = middle - 1
- }
+ // Rotated binary search
+ if nums[left] <= nums[middle] { // Left half is sorted
+ if nums[left] <= target && target < nums[middle] {
+ right = middle - 1
+ } else {
+ left = middle + 1
+ }
+ } else { // Right half is sorted
+ if nums[middle] < target && target <= nums[right] {
+ left = middle + 1
+ } else {
+ right = middle - 1
+ }
+ }
}
return -1 // Target not found
}
Why the Difference?
- In a rotated array, parts of the array are unsorted. You need to:
- Identify which half is sorted.
- Check if the target lies in the sorted half.
- In a normal sorted array, the order is guaranteed, so you don’t need extra checks.
Similar Problem
- Find Minimum in Rotated Sorted Array
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II with Duplicates
- Find Minimum in Rotated Sorted Array II With Duplicates
Please visit https: https://codeandalgo.com for more such contents
Leave a Reply