{"id":25266,"date":"2017-10-15T16:29:37","date_gmt":"2017-10-15T10:59:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25266"},"modified":"2017-10-15T16:29:37","modified_gmt":"2017-10-15T10:59:37","slug":"search-almost-sorted-array","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/search-almost-sorted-array\/","title":{"rendered":"Search in an almost sorted array"},"content":{"rendered":"<p>Given an array which is sorted, but after sorting some elements are moved to either of the adjacent positions, i.e., arr[i] may be present at arr[i+1] or arr[i-1]. Write an efficient function to search an element in this array<span id=\"more-130447\"><\/span>. Basically the element arr[i] can only be swapped with either arr[i+1] or arr[i-1].<\/p>\n<p>For example consider the array {2, 3, 10, 4, 40}, 4 is moved to next position and 10 is moved to previous position.<\/p>\n<p>Example:<\/p>\n<pre>Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 40\r\nOutput: 2 \r\nOutput is index of 40 in given array\r\n\r\nInput: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 90\r\nOutput: -1\r\n-1 is returned to indicate element is not present<\/pre>\n<p>A simple solution is to linearly search the given key in given array. Time complexity of this solution is O(n). We cab modify <a href=\"http:\/\/geeksquiz.com\/binary-search\/\" target=\"_blank\" rel=\"noopener noreferrer\">binary search<\/a> to do it in O(Logn) time.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>The idea is to compare the key with middle 3 elements, if present then return the index. If not present, then compare the key with middle element to decide whether to go in left half or right half. Comparing with middle element is enough as all the elements after mid+2 must be greater than element mid and all elements before mid-2 must be smaller than mid element.<\/p>\n<p>Following is C++ implementation of this approach.<\/p>\n<p><strong>C++<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20an%20element%20in%20an%20almost%20sorted%0A%2F%2F%20array%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20A%20recursive%20binary%20search%20based%20function.%20It%20returns%0A%2F%2F%20index%20of%20x%20in%20given%20array%20arr%5Bl..r%5D%20is%20present%2C%20%0A%2F%2F%20otherwise%20-1%0Aint%20binarySearch(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r%2C%20int%20x)%0A%7B%0A%20%20%20if%20(r%20%3E%3D%20l)%0A%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20mid%20%3D%20l%20%2B%20(r%20-%20l)%2F2%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20element%20is%20present%20at%20one%20of%20the%20middle%20%0A%20%20%20%20%20%20%20%20%2F%2F%203%20positions%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3D%3D%20x)%20%20return%20mid%3B%0A%20%20%20%20%20%20%20%20if%20(mid%20%3E%20l%20%26%26%20arr%5Bmid-1%5D%20%3D%3D%20x)%20return%20(mid%20-%201)%3B%0A%20%20%20%20%20%20%20%20if%20(mid%20%3C%20r%20%26%26%20arr%5Bmid%2B1%5D%20%3D%3D%20x)%20return%20(mid%20%2B%201)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20element%20is%20smaller%20than%20mid%2C%20then%20it%20can%20only%20%0A%20%20%20%20%20%20%20%20%2F%2F%20be%20present%20in%20left%20subarray%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3E%20x)%20return%20binarySearch(arr%2C%20l%2C%20mid-2%2C%20x)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Else%20the%20element%20can%20only%20be%20present%20in%20right%20subarray%0A%20%20%20%20%20%20%20%20return%20binarySearch(arr%2C%20mid%2B2%2C%20r%2C%20x)%3B%0A%20%20%20%7D%0A%20%0A%20%20%20%2F%2F%20We%20reach%20here%20when%20element%20is%20not%20present%20in%20array%0A%20%20%20return%20-1%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main(void)%0A%7B%0A%20%20%20int%20arr%5B%5D%20%3D%20%7B3%2C%202%2C%2010%2C%204%2C%2040%7D%3B%0A%20%20%20int%20n%20%3D%20sizeof(arr)%2F%20sizeof(arr%5B0%5D)%3B%0A%20%20%20int%20x%20%3D%204%3B%0A%20%20%20int%20result%20%3D%20binarySearch(arr%2C%200%2C%20n-1%2C%20x)%3B%0A%20%20%20(result%20%3D%3D%20-1)%3F%20printf(%22Element%20is%20not%20present%20in%20array%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3A%20printf(%22Element%20is%20present%20at%20index%20%25d%22%2C%20result)%3B%0A%20%20%20return%200%3B%0A%7D%0A\u201d message=\u201dc++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>JAVA<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20to%20find%20an%20element%20in%20an%20almost%20sorted%20array%0Aclass%20SearchAlmost%0A%7B%0A%20%20%20%20%2F%2F%20A%20recursive%20binary%20search%20based%20function.%20It%20returns%0A%20%20%20%20%2F%2F%20index%20of%20x%20in%20given%20array%20arr%5Bl..r%5D%20is%20present%2C%0A%20%20%20%20%2F%2F%20otherwise%20-1%0A%20%20%20%20int%20binarySearch(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(r%20%3E%3D%20l)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20mid%20%3D%20l%20%2B%20(r%20-%20l)%2F2%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20element%20is%20present%20at%20one%20of%20the%20middle%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%203%20positions%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3D%3D%20x)%20%20return%20mid%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(mid%20%3E%20l%20%26%26%20arr%5Bmid-1%5D%20%3D%3D%20x)%20return%20(mid%20-%201)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(mid%20%3C%20r%20%26%26%20arr%5Bmid%2B1%5D%20%3D%3D%20x)%20return%20(mid%20%2B%201)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20element%20is%20smaller%20than%20mid%2C%20then%20it%20can%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20only%20be%20present%20in%20left%20subarray%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3E%20x)%20return%20binarySearch(arr%2C%20l%2C%20mid-2%2C%20x)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Else%20the%20element%20can%20only%20be%20present%20in%20right%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20subarray%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20binarySearch(arr%2C%20mid%2B2%2C%20r%2C%20x)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20We%20reach%20here%20when%20element%20is%20not%20present%20in%20array%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20abc%20ob%20%3D%20new%20abc()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B3%2C%202%2C%2010%2C%204%2C%2040%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20int%20x%20%3D%204%3B%0A%20%20%20%20%20%20%20%20int%20result%20%3D%20ob.binarySearch(arr%2C%200%2C%20n-1%2C%20x)%3B%0A%20%20%20%20%20%20%20%20if(result%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Element%20is%20not%20present%20in%20array%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Element%20is%20present%20at%20index%20%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJAVA\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Element is present at index 3<\/pre>\n<p>Time complexity of the above function is O(Logn).<\/p>\n[ad type=\u201dbanner\u201d]\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Search in an almost sorted array &#8211; Searching and Sorting &#8211; A simple solution is linearly search given key in given array.Time complexity of solution is O(n).We cab modify binary search to do it in O(Logn) time.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,71670,83512],"tags":[71128,71222,72388,71133,71893,72390,72302,70892,71121,71135,71134,71141,71131,71130,72305,72392,72389,71144,70895,70017,72386,71160,71158,70969,70075,70914,70046,71714,71265,70272,72695,70016,70548,72387,72385,72299,71695,70020,71161,72391,71149,72384,70967,72303,71156,71219,71142,72190,72185],"class_list":["post-25266","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-searching-and-sorting","category-sorted-array","tag-algorithm-for-bubble-sort","tag-algorithm-for-insertion-sort","tag-algorithm-for-sorting","tag-algorithm-of-bubble-sort","tag-algorithm-sort","tag-array-sorting-algorithm","tag-best-sorting","tag-best-sorting-algorithm","tag-bubble-sort-algorithm","tag-bubble-sort-algorithm-in-data-structure","tag-bubble-sort-algorithm-with-example","tag-bubble-sort-animation","tag-bubble-sort-code","tag-bubble-sort-in-data-structure","tag-c-sort","tag-c-sorting-algorithms","tag-common-sorting-algorithms","tag-different-sorting-algorithms","tag-fastest-sorting-algorithm","tag-insertion-sort-algorithm","tag-insertion-sort-animation","tag-insertion-sort-in-data-structure","tag-java-sort","tag-java-sorting-algorithms","tag-linear-sort","tag-most-efficient-sorting-algorithm","tag-quicksort","tag-quicksort-algorithm-in-data-structure","tag-quicksort-example","tag-search-algorithms","tag-search-in-an-almost-sorted-array","tag-selection-sort-algorithm","tag-selection-sort-in-data-structure","tag-simple-sorting-algorithm","tag-sort-algorithm-c","tag-sort-c","tag-sorted","tag-sorting-algorithms","tag-sorting-algorithms-comparison","tag-sorting-algorithms-examples","tag-sorting-algorithms-in-data-structures","tag-sorting-algorithms-in-data-structures-with-examples","tag-sorting-algorithms-java","tag-sorting-algorithms-visualized","tag-sorting-algorithms-with-examples","tag-sorting-in-c","tag-sorting-in-data-structure","tag-sorting-methods","tag-sortings"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25266","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25266"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25266\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25266"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}